visio网站开发流程图,网站托管西安,做海报设计的网站,化州手机网站建设公司正题
POJ链接:http://poj.org/problem?id1185 jzoj链接:https://jzoj.net/senior/#main/show/1768 洛谷评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP2704 正题
每个炮兵攻击范围是上左下右各2格#xff0c;高山地区不可以放炮兵#xff0c;求所以…正题
POJ链接:http://poj.org/problem?id1185 jzoj链接:https://jzoj.net/senior/#main/show/1768 洛谷评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP2704 正题
每个炮兵攻击范围是上左下右各2格高山地区不可以放炮兵求所以炮兵都无法互相攻击最多能放多少个。 解题思路
用状态压缩dp我们先枚举所有单行合法情况然后在所以情况里枚举然后用3维一个是行数另两个是当行情况和上一行情况然后这样我们就可以用3行情况来判断了。 code
#includecstdio
#includeiostream
#includealgorithm
#includecstring
using namespace std;
int n,m,MS,f[101][61][61],ans,p[101],tot,state[61];
char x;
int count(int x)//计算1的个数
{int ans0;for(int j0;jm;j)if(x(1j)) ans;return ans;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jm;j){cinx;p[i](p[i]1)(xH);}MS1m;for(int i0;iMS;i){int num0;bool okfalse,flagfalse;for(int j0;jm;j)if(ij1) okok|(num2flag),num0,flagtrue;else num;if(!ok)state[tot]i;}//统计可行方案for (int i1;itot;i) if(!(state[i]p[1])){f[1][i][0]count(state[i]);if(n1) ansmax(ans,f[n][i][0]);}//第一行特殊处理for(int i1;itot;i)if(!(state[i]p[2])){for(int j1;jtot;j){if(state[j]p[1]||state[i]state[j]) continue;f[2][i][j]max(f[2][i][j],f[1][j][0]count(state[i]));if(n2) ansmax(ans,f[n][i][j]);}}//第二行特殊处理for(int i3;in;i)for(int j1;jtot;j){if(state[j]p[i]) continue;for(int k1;ktot;k){if(state[k]p[i-1]||state[j]state[k]) continue;//枚举上一行for(int l1;ltot;l){if(state[l]p[i-2] || state[j]state[l] || state[k]state[l])continue;//枚举上第2行f[i][j][k]max(f[i-1][k][l]count(state[j]),f[i][j][k]);//求最大值}if(in)ansmax(ans,f[n][j][k]);//统计最大答案}}printf(%d,ans);
}
