HDU5693

---

做法：

同hdu2476也時兩次dp的題，首先可以列出方程\(f[i] = max(f[i-1], max(f[j-1]+(i-j+1))*can[j][i])\)，\(can[j][i]\)表示從j到i能否完全消除。

現在考慮如何求出\(can[l][r]\)，還是區間dp，任何一個長度≥2的等差數列，都可以拆分為長度為2或3的等差數列的組合，于是可以列出轉移方程，對于\([l,r]\)我們有以下幾種轉移：

• 當a[l],a[r]是符合要求的等差數列時，\(can[l][r] |= can[l+1][r-1]\)
• 當a[l],a[r]不是時，枚舉中間的位置 $ can[l][r] |= (can[l][k-1]·can[k][r]) $
• 當a[l],a[p],a[r] (p時l,r之間的一個位置) 是符合要求的等差數列時，根據情況把區間拆成幾個部分，其中最普通的情況為\(can[l][r] |= can[l+1][p-1]·can[p+1][r-1]\)
• 當不存在這樣的p時，直接枚舉中間位置轉移

實現時，一定要注意細節，一些地方的特判不足都會wa，我這里單獨計算區間長度為2,3的答案才能ac

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back const int N = 300 + 17; const int inf = 0x3f3f3f3f; typedef long long ll; using namespace std; int n, m, f[N]; ll a[N], d; bool can[N][N]; map<ll,bool> M; int fd(int l,int r,ll x) {rep(i,l,r)if(a[i]==x)return i;return -1; } void init_can() {memset(can,0,sizeof(can));rep(i,1,n-1) if(M.find((a[i+1]-a[i]))!=M.end())can[i][i+1]=1;rep(L,3,n) rep(l,1,n-L+1) {int r = l + L - 1;if(L == 3) { //***特判！！！if(a[l+1]*2==a[r]+a[l]&&M.find(a[l+1]-a[l])!=M.end()) can[l][r] = 1;else can[l][r] = 0;continue;}if(M.find((a[r]-a[l]))!=M.end()) {if(l+1==r) can[l][r] = 1;else can[l][r] |= can[l+1][r-1];}int p = fd(l+1,r-1,(a[r]+a[l])/2);if(abs(a[r]-a[l])%2==0&&p!=-1&&M.find((a[r]-a[l])/2)!=M.end()){if(l+1==p&&p+1==r) can[l][r] = 1;else if(l+1==p) can[l][r] |= can[p+1][r-1];else if(p+1==r) can[l][r] |= can[l+1][p-1];else can[l][r] |= (can[p+1][r-1]&can[l+1][p-1]);}rep(k,l+1,r) can[l][r] |= (can[l][k-1]&can[k][r]);} }int main() {//freopen("in.txt","r",stdin);int T;scanf("%d",&T);while(T--) {M.clear();scanf("%d%d",&n,&m);rep(i,1,n) scanf("%I64d",&a[i]);rep(i,1,m) scanf("%I64d",&d),M[d]=1;init_can();memset(f,0,sizeof(f));f[0] = f[1] = 0;rep(i,2,n) {f[i] = f[i-1];rep(j,1,i-1) if(can[j][i]) f[i] = max(f[i],f[j-1]+(i-j+1));}printf("%d\n",f[n]);}return 0; }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9438746.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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