题目描述
司令部的将军们打算在 NM 的网格地图上部署他们的炮兵部队. 一个 NM 的地图由 N 行 M 列组成, 地图的每一格可能是山地 (用 "H" 表示), 也可能是平原 (用 "P" 表示), 如下图. 在每一格平原地形上最多可以布置一支炮兵部队 (山地上不能够部署炮兵部队); 一支炮兵部队在地图上的攻击范围如图中黑色区域所示:
如果在地图中的灰色所标识的平原上部署一支炮兵部队, 则图中的黑色的网格表示它能够攻击到的区域: 沿横向左右各两格, 沿纵向上下各两格. 图上其它白色网格均攻击不到. 从图上可见炮兵的攻击范围不受地形的影响. 现在, 将军们规划如何部署炮兵部队, 在防止误伤的前提下 (保证任何两支炮兵部队之间不能互相攻击, 即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内), 在整个地图区域内最多能够摆放多少我军的炮兵部队.
输入输出格式
输入格式:
第一行包含两个由空格分割开的正整数, 分别表示 N 和 M;
接下来的 N 行, 每一行含有连续的 M 个字符 ('P'或者'H'), 中间没有空格. 按顺序表示地图中每一行的数据. N≤100;M≤10.
输出格式:
仅一行, 包含一个整数 K, 表示最多能摆放的炮兵部队的数量.
输入输出样例
输入样例 #1:
- 5 4
- PHPP
- PPHH
- PPPP
- PHPP
- PHHP
输出样例 #1:
6
题意:
思路:
状压 DP
因为每一行要对下面两行有影响, 所以我们定义 DP 状态就要维护前两行状态的信息, 即
dp[i][j][k] 代表 到第 i 行, 当前行是第 j 个状态, 上一行是第 k 个状态, 最大的部署数量.
我们知道如果一行有 m 个方格, 那么最多有 2^m 个状态, 而 m 最大是 10,
那么如果我们不进行优化, dp 数组要开到 dp[100][1024][1024] 我们应该知道, 这个数组太大了, 我们是开不到这么大的数组的.
那么我们应该如何优化呢? 我们从题目中的一个信息来入手, 每一行一个炮台对左右两个位置都有影响, 那么减去一行中, 两个 1 的距离最少为 3, 这样一来合法的状态数量就少之又少.
通过程序我们可以得知, 合法的状态数不大于 110, 那么我们可以枚举 第 i 合法状态来 DP, 用一个数组 INDEX 来存具体的状态信息, 即 INDEX[i] 为第 i 个合法状态的具体状态信息.
这样我们就优化了时空.
状态转移方程为:
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][w]+num[INDEX[j]]);
细节见代码:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #include <vector>
- #include <iomanip>
- #define ALL(x) (x).begin(), (x).end()
- #define rt return
- #define dll(x) scanf("%I64d",&x)
- #define xll(x) printf("%I64d\n",x)
- #define sz(a) int(a.size())
- #define all(a) a.begin(), a.end()
- #define rep(i,x,n) for(int i=x;i<n;i++)
- #define repd(i,x,n) for(int i=x;i<=n;i++)
- #define pii pair<int,int>
- #define pll pair<long long ,long long>
- #define gbtb iOS::sync_with_stdio(false),cin.tie(0),cout.tie(0)
- #define MS0(X) memset((X), 0, sizeof((X)))
- #define MSC0(X) memset((X), '\0', sizeof((X)))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define eps 1e-6
- #define gg(x) getInt(&x)
- #define chu(x) cout<<"["<<#x<<""<<(x)<<"]"<<endl
- using namespace std;
- typedef long long ll;
- ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
- ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
- ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
- inline void getInt(int* p);
- const int maxn=1000010;
- const int inf=0x3f3f3f3f;
- /*** TEMPLATE CODE * * STARTS HERE ***/
- int n;
- int m;
- int a[500];
- bool can[(1<<11)];
- bool can2[300][123];
- int dp[120][123][123];
- int ans=0;
- int INDEX[maxn];
- int cnt=0;
- int num[(1<<11)];
- int main()
- {
- // freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
- //freopen("D:\\common_text\code_stream\\out.txt","w",stdout);
- gbtb;
- cin>>n>>m;
- char c;
- repd(i,1,n)
- {
- repd(j,1,m)
- {
- cin>>c;
- if(c=='P')
- {
- a[i]=(a[i]<<1)+1;
- }else
- {
- a[i]=(a[i]<<1);
- }
- }
- }
- int maxstate=(1<<m)-1;// 最大状态数
- for(int i=0;i<=maxstate;i++)
- {
- if(((i<<1)&i)==0&&((i<<2)&i)==0&&((i>>2)&i)==0&&((i>>1)&i)==0)// 同一行内两个 1 之间至少要有两个空格
- {
- INDEX[++cnt]=i;
- can[cnt]=1;
- int j=i;
- while(j)
- {
- if(j&1)
- {
- num[i]++;
- }
- j>>=1;
- }
- }
- }
- // can2[i][j] 代表在第 i 行中, 第 j 个状态是合法的状态.
- for(int i=1;i<=cnt;i++)
- {
- int x=INDEX[i];
- if(((x&a[1])==x))
- {
- can2[1][i]=1;
- dp[1][i][0]=num[x];
- }
- }
- for(int i=1;i<=cnt;++i)
- {
- if(((INDEX[i]&a[2])==INDEX[i]))
- {
- can2[2][i]=1;
- for(int j=1;j<=cnt;++j)
- {
- if(can2[1][j])
- {
- if((INDEX[i]&INDEX[j])==0)
- {
- dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+num[INDEX[i]]);
- }
- }
- }
- }
- }
- for(int i=3;i<=n;++i)
- {
- for(int j=1;j<=cnt;j++)
- {
- if(((INDEX[j]&a[i])==INDEX[j]))
- {
- can2[i][j]=1;
- for(int k=1;k<=cnt;k++)
- {
- if(can2[i-1][k])
- {
- if((INDEX[k]&INDEX[j])==0)
- {
- for(int w=1;w<=cnt;++w)
- {
- if(can2[i-2][w])
- {
- if((INDEX[w]&INDEX[j])==0&&(INDEX[w]&INDEX[k])==0)// 和上面两行均没重合的 1
- dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][w]+num[INDEX[j]]);
- }
- }
- }
- }
- }
- }
- }
- }
- for(int i=1;i<=cnt;++i)
- {
- for(int j=1;j<=cnt;j++)
- {
- ans=max(ans,dp[n][i][j]);
- }
- }
- cout<<ans<<endl;
- return 0;
- }
- inline void getInt(int* p) {
- char ch;
- do {
- ch = getchar();
- } while (ch == '' || ch =='\n');
- if (ch == '-') {
- *p = -(getchar() - '0');
- while ((ch = getchar())>= '0' && ch <= '9') {
- *p = *p * 10 - ch + '0';
- }
- }
- else {
- *p = ch - '0';
- while ((ch = getchar())>= '0' && ch <= '9') {
- *p = *p * 10 + ch - '0';
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3117026.html