2013腾讯编程马拉松复赛第二场部分题解

最近真是太水啦，就拿昨天的比赛来说，只过了一道。。。，最后一道因为一个变量写反啦，一直WA到比赛结束，直接导致我没有看到1002这道大水题。。。唉，看来我真不是比赛型选手，今天把1005和1002做了下，补个题解吧。

http://acm.hdu.edu.cn/showproblem.php?pid=4535

吉哥系列故事——礼尚往来

吉哥还是那个吉哥
　　那个江湖人称“叽叽哥”的基哥
　　
　　每当节日来临，女友众多的叽叽哥总是能从全国各地的女友那里收到各种礼物。
　　有礼物收到当然值得高兴，但回礼确是件麻烦的事！
　　无论多麻烦，总不好意思收礼而不回礼，那也不是叽叽哥的风格。
　　
　　现在，即爱面子又抠门的叽叽哥想出了一个绝妙的好办法：他准备将各个女友送来的礼物合理分配，再回送不同女友，这样就不用再花钱买礼物了！
　　
　　假设叽叽哥的n个女友每人送他一个礼物（每个人送的礼物都不相同），现在他需要合理安排，再回送每个女友一份礼物，重点是，回送的礼物不能是这个女友之前送他的那个礼物，不然，叽叽哥可就摊上事了，摊上大事了......
　　
　　现在，叽叽哥想知道总共有多少种满足条件的回送礼物方案呢？

1001：有公式的，亏我还推了半天，数据量也不大，直接根据公式推就行，水题就不说了。。。

http://acm.hdu.edu.cn/showproblem.php?pid=4536

XCOM Enemy Unknown#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>#include <vector>using namespace std;int dp[200][200][200];vector<int> a[11];int check(int x,int len){ int i; for(i=0;i<len-2;i++) { int tmp=(1<<i)+(1<<(i+2)); if((tmp&x)==tmp) { return 0; } } return 1;}int cot[1100];int getnum(int x){ int sum=0; while(x) { if(x%2) sum++; x/=2; } return sum;}void init(){ int i,j,tmp; for(i=0;i<=1024;i++) cot[i]=getnum(i); for(i=1;i<=10;i++) { tmp=(1<<i)-1; a[i].push_back(0); for(j=1;j<=tmp;j++) { if(check(j,i)) { a[i].push_back(j); } } }}int max(int a,int b){ return a>b?a:b;}int num[110];int main(){ init(); int n,m,x; while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,0,sizeof(dp)); int i,j,tmp; for(i=1;i<=n;i++) { tmp=0; for(j=1;j<=m;j++) { scanf("%d",&x); tmp=tmp*2+x; } num[i]=tmp; } tmp=a[m].size(); int ans=0; for(i=0;i<tmp;i++) { if((num[1]|a[m][i])==num[1])//判断是否满足棋盘 { int now=a[m][i]; dp[1][0][i]=cot[now]; ans=max(ans,dp[1][0][i]); } } for(i=2;i<=n;i++) { for(j=0;j<tmp;j++) { if((num[i]|a[m][j])==num[i])//状态满足第i行 { int now=a[m][j]; int s,t; for(s=0;s<tmp;s++) { int pre=a[m][s]; if((num[i-1]|pre)==num[i-1]) { if(((now<<1)&pre)==0&&((now>>1)&pre)==0) { if(i==2) dp[i][s][j]=dp[1][0][s]+cot[now]; else { for(t=0;t<tmp;t++) { int ppre=a[m][t]; if((num[i-2]|ppre)==num[i-2]) { if((ppre&now)==0) { if(((ppre<<1)&pre)==0&&((ppre>>1)&pre)==0) dp[i][s][j]=max(dp[i][s][j],dp[i-1][t][s]+cot[now]); } } } } ans=max(ans,dp[i][s][j]); } } } } } } printf("%d\n",ans); } return 0;}