XHTML

浏览数：16 / 时间：2015年06月09日

　　简单的差分约束模型 , 因为d是定值 , 所以也可以按最短路理解 , trick是不能把圈算进去.

 1 #define maxn 55
 2 class Egalitarianism {
 3 public:
 4     int maxDifference(vector <string>, int);
 5 };
 6 int e[maxn][maxn],n,f[maxn][maxn];
 7 int Egalitarianism::maxDifference(vector <string> isFriend, int d) {
 8     n = isFriend.size();
 9     memset(e,-1,sizeof(e));
10     for (int i=0 ; i<n ; i++ ) {
11         for (int j=0 ; j<n ; j++ ) if (isFriend[i][j]==‘Y‘) {
12             e[i][j] = d;
13         }
14     }
15     int ans = -1;
16     for (int k=0 ; k<n ; k++ ) {
17         for (int i=0 ; i<n ; i++ ) {
18             for (int j=0 ; j<n ; j++ ) if (e[i][k] != -1 && e[k][j] != -1) {
19                 if (e[i][j]==-1 || e[i][j]>e[i][k] + e[k][j])
20                     e[i][j] = e[i][k]+e[k][j];
21             }
22         }
23     }
24     for (int i=0 ; i<n ; i++ ) for (int j=0 ; j<n ; j++ )  if (i!=j){
25         if (e[i][j] == -1) return -1;
26         ans = max(ans,e[i][j]);
27     }
28     return ans;
29 }

View Code

　　计数模型很好想 , 但是有很多细节要想清楚 , 一开始想简单了......

　　离散化之后 , dp[i][j][k] 表示满足要求的方案数:

　　(1) 挖了前i种东西;

　　(2) 所以挖出来的东西最大深度为j;

　　(3) 挖出来了k个;

　　(4) 每个都是在found里出现的;

　　然后 ans = sigma ( dp[51][j][k] * factor[j][k] ) (1<=j<INF , found.size()<=j<=K);

　　比较麻烦的地方在对于给定的状态 , 计算对应factor:

　　(1) 还要挖 K-k个 , 并且他们的深度大于j , 即不能被发现;

　　(2) 要把所有的building考虑进去,而不仅仅是不在found里面的;

　　(3) 必须保证接下来挖的中,深度最小的building未在found里出现 , 否则会重复计数;

  1 using namespace std;
  2 #define maxn 60
  3 #define maxd 100010
  4 #include <cstring>
  5 const int INF = maxd-1;
  6 typedef long long llong;
  7 
  8 class Excavations {
  9 public:
 10     long long count(vector <int>, vector <int>, vector <int>, int);
 11 };
 12 
 13 bool in[maxn];
 14 llong c[maxn][maxn] , b[maxn][maxn][maxn] ;//, s[maxn][maxn][maxn] , s2[maxn][maxn][maxn];
 15 int cnt[maxn],n,m,D;
 16 map<int,int> hk , hd;
 17 vector<int> bufk , bufd , t[maxn];
 18 
 19 struct node{
 20     int k,d;
 21 };node build[maxn];
 22 
 23 bool cmp (node a , node b) {
 24     if (a.k == b.k) return a.d<b.d;
 25     return a.k<b.k;
 26 }
 27 void pretreat(vector<int> kind,vector<int> depth,vector<int> found) {
 28     n = kind.size();
 29     m = found.size();
 30     bufd.push_back(0);
 31     bufd.push_back(INF);
 32     bufk.push_back(0);
 33     for (int i=0 ; i<n ; i++ ) bufk.push_back(kind[i]) , bufd.push_back(depth[i]);
 34     sort(bufd.begin(),bufd.end());
 35     sort(bufk.begin(),bufk.end());
 36     bufd.erase( unique(bufd.begin(),bufd.end()) , bufd.end() ) ;
 37     bufk.erase( unique(bufk.begin(),bufk.end()) , bufk.end() ) ;
 38     for (int i=0 ; i<(int)bufk.size() ; i++ ) hk[bufk[i]] = i;
 39     for (int i=0 ; i<(int)bufd.size()  ; i++ ) hd[bufd[i]] = i;
 40     for (int i=0 ; i<n ; i++ ) build[i] = (node){hk[kind[i]] , hd[depth[i]]};
 41     sort(build,build+n,cmp);
 42     for (int i=0 ; i<m ; i++ )    in[hk[found[i]]] = 1;
 43     for (int i=0 ; i<=50 ; i++ ) {
 44         c[i][0] = 1;
 45         for (int j=1 ; j<=i ; j++ ) c[i][j] = c[i-1][j-1] + c[i-1][j];
 46     }
 47     D = hd[maxd-1];
 48     for (int i=0 ; i<=D ; i++ ) {
 49         for (int j=0 ; j<n ; j++ ) if (build[j].d>=i)
 50             cnt[i] ++;
 51     }
 52     for (int i=0 ; i<n ; i++ ) t[build[i].k].push_back(build[i].d);
 53     for (int i=0 ; i<=50 ; i++ ) sort(t[i].begin() , t[i].end());
 54 }
 55 
 56 long long Excavations::count(vector <int> kind, vector <int> depth, vector <int> found, int K) {
 57     pretreat(kind,depth,found);
 58 
 59     b[0][0][0] = 1;
 60     for (int i=0 ; i<51 ; i++ )
 61     for (int j=0 ; j<D ; j++ )
 62     for (int k=0 ; k<=K ; k++ ) if (b[i][j][k]) { //printf("b[%d][%d][%d]=%lld\n",i,j,k,b[i][j][k]);
 63         
 64         int debug = 0;
 65         if (j==11) debug = 1;
 66         
 67         if (in[i+1]) {// printf("t[%d].size()=%d\n",i+1,(int)t[i+1].size()); for (int x=0 ; x<(int)t[i+1].size() ; x++ ) printf("%d ",t[i+1][x]); printf("\n");
 68             for (int x=0 ; x<(int)t[i+1].size() ; x++ )
 69             for (int y=0 ; y<=x ; y++ ) {
 70                 if (y+1+k>K) break;
 71                 int dep = max(j, t[i+1][x]);
 72                 b[i+1][dep][y+1+k] += b[i][j][k] * c[x][y];
 73                 if (debug) {
 74             //        printf("b[%d][%d][%d] add %lld * c[%d][%d](%lld) = %lld\n",i+1,dep,y+1+k,b[i][j][k],x,y,c[x][y],b[i][j][k]*c[x][y]);
 75                 }
 76             }
 77         } else {
 78             b[i+1][j][k] += b[i][j][k];
 79         //    if (debug) printf("b[%d][%d][%d] add %lld\n",i+1,j,k,b[i][j][k]);
 80         }
 81     }
 82     llong ans = 0;
 83 
 84     vector<int> illegal;
 85     int f[maxn];
 86     memset(f,0,sizeof(f));
 87     for (int i=0 ; i<n ; i++ ) if (!in[build[i].k]) {
 88         illegal.push_back(build[i].d);
 89         f[build[i].d] ++ ;
 90     }
 91     sort(illegal.begin(),illegal.end());
 92     illegal.erase( unique(illegal.begin(),illegal.end()) , illegal.end() );
 93 
 94     for (int i=1 ; i<D ; i++ )
 95     for (int j=m ; j<=K ; j++ ) if (b[51][i][j]) {
 96         if (j==K) {
 97             ans += b[51][i][j];
 98             printf("add: b[%d][%d]=%lld\n",i,j,b[51][i][j]);
 99         }
100         else {
101             llong fct = 0;
102             for (int x=0 ; x<(int)illegal.size() ; x++ ) if (illegal[x]>i) {
103                 int d = illegal[x];
104                 int need = K-j;
105                 for (int y=1 ; y<=need && y<=f[d] ; y++ ) {
106                     fct += c[f[d]][y] * c[cnt[d]-f[d]][need-y];
107                     printf("fct add: c[%d][%d] * c[%d][%d] = %lld\n",f[d],y,cnt[d]-f[d],need-y,c[f[d]][y]*c[cnt[d]-f[d]][need-y]);
108                 }
109             }
110             ans += b[51][i][j] * fct;
111         }
112     }
113     return ans;
114 }