jQuery AJAX — 篇二 $.get()和 $.post()
跟poj 1185 炮兵阵地差不多。
此题由于士兵不能安排在曼哈顿距离为2的地方。
所以只要不是类似:
第i-2行: 010 | 010 | |
第i-1行: 000 | 100 | 001 |
第i行: 010 | | 010 | 1 01
1】同一列隔一行的位置都有士兵。
2】上下行的隔1位有士兵。
3】同一行隔1个的地方有士兵。
dp[i][k][j]和炮兵阵地表示的意义是一样的。第i行的状态为j,第i-1行的状态为k。
转移方程:dp[i][k][j]=max(dp[i][k][j],dp[i-1][t][k]+num[j])。
就可以了。。
啊啊啊啊啊。。。我本来想直接在炮兵阵地的代码上改,不知道哪里粗心,怎么都是wa。。
后来只得重写一遍。。。。所幸这次1a,。。。快吐了。。。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int dp[202][202][202]; int cur[202],ok[202],num[202]; int maxx(int x,int y) { return x>y?x:y; } int count_1(int x) { int sum=0; while(x) { if(x&1) sum++; x>>=1; } return sum; } int main() { int n,m,ans,mp; while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,-1,sizeof(dp)); memset(cur,0,sizeof(cur)); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&mp); if(mp==0) cur[i]|=(1<<j); } } int tot=(1<<m); int cnt=0; for(int i=0;i<tot;i++) { if((i&(i<<2))==0) { ok[cnt]=i; num[cnt++]=count_1(i); } } for(int i=0;i<cnt;i++) { if((ok[i]&cur[0])==0) dp[0][0][i]=num[i]; } for(int i=1;i<n;i++) { for(int j=0;j<cnt;j++) { if(cur[i]&ok[j]) continue; for(int k=0;k<cnt;k++) { if(ok[j]&(ok[k]<<1)) continue; if(ok[j]&(ok[k]>>1)) continue; for(int t=0;t<cnt;t++) { if((ok[t]&ok[j])||(ok[k]&(ok[t]>>1))||(ok[k]&(ok[t]<<1))) continue; if(dp[i-1][t][k]==-1) continue; dp[i][k][j]=maxx(dp[i][k][j],dp[i-1][t][k]+num[j]); } } } } ans=0; for(int i=0;i<cnt;i++) { for(int j=0;j<cnt;j++) { if(ans<dp[n-1][i][j]) ans=dp[n-1][i][j]; } } printf("%d\n",ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。