首先，我們從集合角度重新看待DP：
直接看題：https://www.acwing.com/problem/content/1029/
就是取紙條的原題，我們令f[i1,j1,i2,j2]表示從(1,1),(1,1)分別走到(i1,j1),(i2,j2)的路徑的max
i1+j1==i2+j2，于是我們可以把狀態變為f[k,i1,i2]表示走到(i1,k-i1),(i2,k-i2)的最大值。
對于最后一個狀態，我們可以按照上下分成4中，同時轉移時重合的化加w[i][j]，否則就分別加一個
下面是AC代碼：
#include <iostream>
#include <algorithm>using namespace std;const int N = 15;int n;
int w[N][N];
int f[N * 2][N][N];int main()
{scanf("%d", &n);int a, b, c;while (cin >> a >> b >> c, a || b || c) w[a][b] = c;for (int k = 2; k <= n + n; k ++ )for (int i1 = 1; i1 <= n; i1 ++ )for (int i2 = 1; i2 <= n; i2 ++ ){int j1 = k - i1, j2 = k - i2;if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){int t = w[i1][j1];if (i1 != i2) t += w[i2][j2];int &x = f[k][i1][i2];x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);x = max(x, f[k - 1][i1 - 1][i2] + t);x = max(x, f[k - 1][i1][i2 - 1] + t);x = max(x, f[k - 1][i1][i2] + t);}}printf("%d\n", f[2*n][n][n]);return 0;
}
接題：https://www.acwing.com/problem/content/189/
看到數據范圍可以確定爆搜（BFS因為一層層存儲量太大不推薦），這樣就轉換成導彈攔截的思路了：從前往后，對于一個導彈找到比他高的min插入即可，若沒有就再開一個（注意防御系統一定是遞增的）
下面是AC代碼：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10001];
int ans=50;
int up[100010],down[10000];
void dfs(int x,int u,int d)
{if(u+d>=ans) return;if(x==n+1){ans=min(ans,u+d);return;}//先上int f=-1;for(int i=1;i<=u;i++){if(up[i]>a[x]){f=i;break;}if(i==u) f=-1;}if(f==-1){up[u+1]=a[x];dfs(x+1,u+1,d);up[u+1]=0;}else{int t=up[f];up[f]=a[x];dfs(x+1,u,d);up[f]=t;}f=-1;for(int i=1;i<=d;i++){ if(down[i]<a[x]){f=i;break;}if(i==d) f=-1;}if(f==-1){down[d+1]=a[x];dfs(x+1,u,d+1);down[d+1]=0;}else{int t=down[f];down[f]=a[x];dfs(x+1,u,d);down[f]=t;}
}
int main()
{while(cin>>n){if(!n) break;for(int i=1;i<=n;i++) cin>>a[i];memset(up,0,sizeof(up));memset(down,0,sizeof(down));ans=50;dfs(1,0,0);cout<<ans<<endl;}
}
接題：https://www.acwing.com/problem/content/1018/
確定f[i][j]的集合：由第一個序列前i個字母，第二個前j個并以b[j]的公共上升子序列。
表示max,然后考慮計算：先按是否包含a[i]分成兩類：不包含：f[i-1][j],包含：a[i]==b[j]
我們又可以把b分為以b[1]...b[j-1]以及空,對于b[k]就是f[i-1][k]+1
下面是AC代碼：
#include<bits/stdc++.h>
using namespace std;
int n,a[100010],b[100010];
int dp[3010][3005];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++){int maxv=0;for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j];if(a[i]==b[j]){dp[i][j]=max(dp[i][j],1);dp[i][j]=max(dp[i][j],maxv);}if(b[j]<a[i]) maxv=max(maxv,dp[i-1][j]+1);}}int res=0;for(int i=1;i<=n;i++) res=max(res,dp[n][i]);cout<<res;
}
)
