棋盘放车问题
问题描述：
在n*n(n≤20)的方格棋盘上放置n个车,求使它们不能互相攻击的方案总数。
问题分析：车子的攻击是直线的上下和左右的。那么我们可以认为是一行一行扫描过来。有dp[i][j]。j表示排列状况
但是根据24点游戏的经验。我们完全可以直接根据排列状况来划分状态。（状态本身就是答案。）
0001 是由 0000得来的。
0011 是由 0010 + 0001得来的。
状态压缩的真正厉害之处不是以物体为刷层。而是以序列来刷层。并且一个循环过去。是从小到大有方向性的刷层。
（也许我可以用2种方法来写24点游戏）。一般来说还是刷层的方法比较好。。去处法DP。
#include<stdio.h> #include<string.h> int dp[30000]; // 8个棋盘 130个 n范围是9个棋盘 int main() { int n,i,j; while(scanf("%d",&n)!=EOF) { memset(dp,0,sizeof(dp)); dp[0] = 1; //还没填 对于不摆当然是1啦。 for(i=1; i<= (1<<n)-1;i++) //n个1,这一层是状态的扫描。 { for(j=i;j>0;j -= (j&-j)) { dp[i] += dp[i-(j&-j)]; //这个dp 是由当前的数的位置(i-(j&-j))的不同而获得的值 } } printf("%d ",dp[(1<<n)-1]); } return 0; }
对当前行进行判断处理可否进行放置。
抓住论文上的状态转移。用来源法来只考虑相关的。不要想偏！
/* input: 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 4 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 2 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 */ #include<stdio.h> #include<string.h> int map[5][5]; int A[5]; int one[5]; void init() { int i,j; for(i=1;i<=4;i++) { A[i] = 0; for(j=1;j<=4;j++) { A[i] = (A[i]<<1) + map[i][j]; } } } int dp[(1<<4)+1]; void solve() { int i,j,temp,top; memset(dp,0,sizeof(dp)); dp[0] = 1; for(i=1;i<1<<4;i++) { temp = i; top = 0; while(temp) { one[++top] = temp&(-temp); temp ^= one[top]; } for(j=1;j<=top;j++) { if((one[j] & A[top])==0) { dp[i] += dp[i-one[j]]; } } } } int main() { int i,j; for(i=1;i<=4;i++) { for(j=1;j<=4;j++) { scanf("%d",&map[i][j]); } } init(); solve(); printf("%d ",dp[(1<<4)-1]); }
/* 给出一个n*m 的棋盘(n、m≤80,n*m≤80)，要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻。 */ #include<stdio.h> int num[300]; // 第i个状态的1的个数 int state[300]; // 存储状态用的 int dp[10][1<<8+1][21];//i j k int M;// M 位的数 int top; //state代表着路径 void DFS(int st,int count,int t,bool flag) { if(t==M) { state[++top] = st; num[top] = count; return; } DFS(st<<1,count,t+1,true); if(flag) { DFS(st<<1|1,count+1,t+1,false); } } //DFS预处理出合法状态 int main() { int i,j,k,q; int N,maxn; while(scanf("%d%d%d",&N,&M,&maxn)!=EOF) { top = 0; if(N<M) //M比较小 { int temp = N; N = M; M = N; } DFS(0,0,-1,false); dp[0][1][0] = 1; //dp中间的那个状态需要注意 变成数组的下标代替了。 //由于这种方法 所以请保证数组第一个位的状态是 0 for(i=1;i<=N;i++) { for(j=1;j<=top;j++) //当前行的第j个状态 { for(q=1;q<=top;q++) //上一行的第q个状态 { for(k=num[j];k<=maxn;k++) { if((state[j]&state[q])==0) { dp[i][j][k] += dp[i-1][q][k-num[j]]; } } } } } int sum = 0; for(i=1;i<=top;i++) { sum += dp[N][i][maxn]; } printf("%d ",sum); } }
炮兵布阵问题
#include<stdio.h> #include<string.h> int num[61]; //同下。 int s[61]; // 合法的状态数。 int A[102]; int dp[102][61][61]; int N,M; int max(int a,int b) { return a>b?a:b; } void init() { memset(A,0,sizeof(A)); int i,j,state; char string[12]; memset(string,0,sizeof(string)); for(i=1;i<=N;i++) { state = 0; scanf("%s",string); for(j=1;j<=M;j++) { if(string[j-1]=='P'){state <<= 1;} else{state = (state<<1|1);} } A[i] = state; } } //存地图 int top; //init = 0 void DFS(int t,int count,int state,int flag) // 0 0 0 0 { if(t==M) { s[++top] = state; num[top] = count; return; } DFS(t+1,count,state<<1,flag+1); if(flag>=2) { DFS(t+1,count+1,state<<1|1,0); } } //存状态 和 数目 /* 解决最多摆放我军的军队。不同状态取max 思考状态转移方程。 不用抽取出来1 我得思考一下抽取1 其实是抽取当前行能摆放的状态罢了 if((s[j]&A[i]==0)&&(s[j]&s[p]==0)&&(s[j]&s[q]==0)) { dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][q]+num[j]); } //j是当前行的棋子情况 k是上一行的棋子情况。 q是上上行的情况。 dp[i][j][k] 若j是非法的状态。那么就为0。别想太多。如果觉得这行不用取的话。那么有0方案可以替代掉。所以我们只考虑当前 另外我被)坑了。二进制运算符可真是低等级的运算 另外dp[i][j][k] 维度的设计其实是为了下一个状态。而形成有推导关系的,所以我们在思考维度的时候需要注意了。 */ void solve() { int i,j,k,q; memset(dp,0,sizeof(0)); for(i=1;i<=N;i++) { for(j=1;j<=top;j++) { for(k=1;k<=top;k++) { for(q=1;q<=top;q++) { if((s[j]&s[k])==0&&(s[j]&s[q])==0) { if((s[j]&A[i])==0) { dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][q]+num[j]); } } } } } } int maxn; maxn = 0; for(i=1;i<=top;i++) { for(j=1;j<=top;j++) { if(dp[N][i][j]>maxn){maxn = dp[N][i][j];} } } printf("%d ",maxn); } int main() { while(scanf("%d%d",&N,&M)!=EOF) { top = 0; init(); DFS(0,0,0,2); solve(); } } /* void DFS(int t,int state,int count,bool flag) { if(t==M) { s[++top] = state; num[top] = count; } DFS(t+1,state<<1,count,1); if(flag) { DFS(t+1,state<<1|1,count+1,0); } } */ /* 5 4 PHPP PPHH PPPP PHPP PHHP 6 3 3 PHP HPH PHP 理论上是 3 我却是 4 如果是连下来的话 */
ZOJ 3802
/*#include<stdio.h> #include<string.h> int max(int a,int b){return a>b?a:b;} int getone(int x) { return (x&(-x)); } /* 1 2 3 4 5 2 4 8 16 32 一共有最多20个数字。 20*16 = 320 的和并后最大的数字。 我只用表示到160个。因为单个就是这样 而160 对应上表。2 -> 1 那么。2^(位数) >160 即8位到达256。 int dp[20][300]; /* int num[20]; int N; void solve() { int i,j; memset(dp,-1,sizeof(dp));//因为状态规定了。必须是那样的状态其他的是非法的。 dp[0][0] = 0; for(i=1;i<=N;i++) { for(j=0;j<256;j++) //这个是状态。 { if(dp[i-1][j]!=-1) { int nownum = num[i]; int nows = j; int nowval = nownum; dp[i][j] = max(dp[i][j],dp[i-1][j]); //第一个作用 while((getone(nows)==(nownum>>1))) { nowval += (nownum<<1); nows ^= getone(nows); //这里的状态不再只是表示局势。 还表示出了数值。 nownum <<= 1; } //合并操作 if(getone(nows) < (nownum>>1)){nows = 0;} nows |= (nownum>>1); //这个数比最小的大 这个数比最小的小 第2 3 个情况 dp[i][nows] = max(dp[i][nows],dp[i-1][j]+nowval); } } } int maxn; maxn = 0; for(i=0;i<256;i++) { if(dp[N][i]>maxn){maxn = dp[N][i];} } printf("%d ",maxn); } int main() { int i; while(scanf("%d",&N)!=EOF) { for(i=1;i<=N;i++) { scanf("%d",&num[i]); } solve(); } }