BZOJ 3193: [JLOI2013]地形生成 计数 + 组合 + 动态规划

#include <cstdio>  
#include <cstring>        
#include <algorithm> 
#define N 1009 
#define mod 2011   
#define ll long long 
#define setIO(s) freopen(s".in", "r" , stdin)   
using namespace std; 
int n ; 
struct Node 
{
    int key, h; 
}t[N];     
bool cmp(Node a, Node b) 
{
    return a.h == b.h ? a.key < b.key : a.h > b.h;   
} 
namespace case1 
{ 
    int f[N], key[N], tmp[N];    
    int main() 
    {  
        int i ;     
        f[0] = 1;   
        for(i = 1; i <= n ; ++ i) 
        { 
            key[i] = t[i].key;         
            if(t[i].h == t[i - 1].h) key[i] += tmp[i - 1], tmp[i] = tmp[i - 1] + 1;    
            else tmp[i] = 1;   
            f[i] = (ll) (f[i - 1] * min(key[i],  i)) % mod;      
        }    
        printf("%d ", f[n]);  
        return 0;    
    } 
};  
namespace case2
{ 
    int f[N];      
    int main() 
    {
        int i , j, k, pos, ans = 1; 
        for(i = 1 ; i <= n ; i = pos + 1) 
        { 
            pos = i; 
            while(pos < n && t[pos + 1].h == t[pos].h) ++ pos;  
            memset(f, 0, sizeof(f)), f[0] = 1;           
            for(j = i ; j <= pos ; ++ j) 
                for(k = 1 ; k <= min(i - 1, t[j].key - 1); ++ k) 
                    f[k] = (f[k] + f[k - 1]) % mod;    
            int re = 0;   
            for(j = 0; j <= min(i - 1, t[pos].key - 1) ; ++ j) re = (re + f[j]) % mod;  
            ans = ans * re % mod;        
        }   
        printf("%d\n", ans);     
        return 0; 
    }
}; 
int main() 
{
    //   setIO("input");     
    int i , j; 
    scanf("%d", &n);    
    for(i = 1; i <= n ; ++ i) 
        scanf("%d%d", &t[i].h, &t[i].key);    
    sort(t + 1, t + 1 + n, cmp);      
    case1::main(), case2::main();  
    return 0; 
}