題目：

n*m個網格，有平原，有山地，平原可以放部隊，部隊攻擊范圍如圖（不受地形影響）（H為山地，P為平原）

題解：

確定狀態：
因為每個炮可以打到兩行，所以每一行放置方式與他放置的情況有關
dp[i][j][k]表示第i行為狀態j，第i-1行為狀態k時所用的最大炮兵數
也就是同時記錄兩行狀態，根據已知的兩行狀態推下一行
狀態轉移：
dp[i][j][p]=max(dp[i][j][p],dp[i-1][p][q]+num[j])
q被枚舉
第i行狀態：j
第i-1行狀態：p
第i-2行狀態：q
j，p，q不能發生沖突
任意1左右兩邊兩位都不是1
((i&(i>>1))==0) && ((i&(i>>2)) ==0)
且1的位置必須是平原
優化：保存符合條件的二進制串，只枚舉自身符合要求的二進制串

代碼：

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> using namespace std; typedef long long ll; //#define ll long long const ll N = 2e3 + 20; const int maxn = 5e5 + 20; const ll mod = 1000000007; ll inv[maxn], vis[maxn], dis[maxn], head[maxn], dep[maxn], out[maxn]; ll fac[maxn], a[maxn], b[maxn], c[maxn], pre[maxn], cnt, sizx[maxn]; vector<ll> vec; char s[maxn]; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p> > m; ll sum[maxn]; ll max(ll a, ll b) { return a > b ? a : b; } ll min(ll a, ll b) { return a < b ? a : b; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } map<ll, ll> mp; ll ksm(ll a, ll b) {a %= mod;ll ans = 1ll;while (b){if (b & 1)ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1ll;}return ans; } ll lowbit(ll x) {return x & (-x); } //int dx[105], dp[105], nc[105], w[105]; int dp[105][105][105];//存i行,第j狀態,和上一行的k狀態的最大炮兵數量 int stk[N], np[N], sp[105];//行合法狀態，合法狀態的炮兵個數，山地的分布01串 int getsum(int x)//求x的二進制狀態中炮兵的數量 {int ans = 0;while (x){if (x & 1)ans++;x >>= 1;}return ans; } int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t, n, m, k;// cin>>t;// while(t--)// {string s;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> s;for (int j = m - 1; j >= 0; j--)if (s[j] == 'H')sp[i] += (1 << j);//累加得每一行山地的分布串}// }k = 1;for (int i = 0; i < (1 << m); i++)//枚舉長度為m的可行狀態{if ((!(i & (i << 1))) && (!(i & (i << 2))))stk[k] = i, np[k++] = getsum(i);}for (int i = 1; i < k; i++)//初始化dp[][][]第一行{if (!(sp[1] & stk[i]))dp[1][i][1] = np[i];}for (int i = 2; i <= n; i++){for (int j = 1; j < k; j++){if (sp[i] & stk[j])//判斷當前狀態和山地是否重疊continue;for (int x = 1; x < k; x++){if ((stk[x] & sp[i - 1]) || (stk[x] & stk[j]))//判斷當前狀態和山地和上一個狀態是否有重疊continue;for (int y = 1; y < k; y++){if ((stk[y] & stk[x]) || (stk[y] & stk[j]) || (stk[y] & sp[i - 2]))continue;//判斷當前狀態和山地和上一個狀態，和上上一個狀態是否有重疊dp[i][j][x] = max(dp[i][j][x], dp[i - 1][x][y] + np[j]);}}}}ll ans = 0;//枚舉第n層所有狀態的最大值for (int i = 1; i < k; i++){for (int j = 1; j < k; j++){ans =max(ans,dp[n][i][j]);}}cout << ans << endl; }

總結

以上是生活随笔為你收集整理的NC16886 炮兵阵地的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。