目录
一、引入：括号匹配
模板
2.最长回文子序列
给你一个长度为n的序列，求最长回文子序列长度
法一：不会区间dp也可以写，把原串与它倒过来的串求最长公共子序列
法二：区间dp
下面这段代码没找到原题 提交，所以就是“应该可能”是对的…
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s;
const int M=1e4+5;
int f[M][M],ans;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s;
int n=s.size();
s=s+s;
for(int i=0;i<2*n;i++)f[i][i]=1;
for(int l=2;l<=n;l++){
for(int i=0;i+l<=2*n;i++){
int j=i+l-1;
if(s[i]==s[j])f[i][j]=f[i+1][j-1]+2;
else f[i][j]=max(f[i+1][j],f[i][j-1]);
}
}
for(int i=0;i<n;i++)
ans=max(ans,f[i][i+n-1]);
cout<<ans;
return 0;
}扩展：求最长回文子串（要连续）
1.最优的：马拉车（mnacher）算法（我个fw没学…）
2.但也可以用dp来做：(O(n^2))
此时，f[i][j]如果等于i~j的最长回文子串长度，比如f[5][10]=3,那么当f[4]==f[11]时，我们并不知道序列5~10中取的那3个是靠前还是靠后或是取中间一段，那么我们就无法转移，只有当f[5][10]==6的时候，即等于i~j的区间长度时，那么s[i-1]和s[j+1]可以加在两端，也即只有这种情况才是有用的，那么我们不如将f[i][j]作为一个bool数组，判断 i ~ j 这一段是不是回文。
那么就只有在(s[i]==s[j]&&f[i+1][j-1]==1)时，f[i][j]=1;
下面的代码是AC了的。。
#include<iostream>
#include<string>
using namespace std;
string s;
const int M=1e4+5;
int f[M][M],ans;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s;
int n=s.size();
s+=s;
for(int l=2;l<=n;l++){ //枚举长度
for(int i=0;i<=n;i++){ //枚举起点
int j=i+l-1; //终点
if(s[i]==s[j]&&(j-i<3||f[i+1][j-1]))
f[i][j]=1;
if(f[i][j])ans=max(ans,j-i+1);
}
}
cout<<ans;
return 0;
}3.石子合并
AC代码:
#include<iostream>
#include<cstring>
const int M=410,inf=0x3f3f3f3f;
int n,a[M],sum[M],ma[M][M],mi[M][M];
using namespace std;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
memset(mi,0x3f,sizeof mi);
for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
//注意初始化mi[i][i]=0;这样后面转移的时候，以2为最小长度枚举时:
//mi[1][2]=min(mi[1][2],mi[1][1]+mi[2][2]+sum[2]-sum[0])才没错
for(int i=1;i<=2*n;i++)mi[i][i]=0,sum[i]=sum[i-1]+a[i];
for(int l=2;l<=n;l++){
for(int i=1;i+l-1<=2*n;i++){
int j=i+l-1;
for(int k=i;k<j;k++){
mi[i][j]=min(mi[i][j],mi[i][k]+mi[k+1][j]+sum[j]-sum[i-1]);
ma[i][j]=max(ma[i][j],ma[i][k]+ma[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int minn=inf,maxx=0;
for(int i=1;i<=n;i++){
minn=min(minn,mi[i][i+n-1]);
maxx=max(maxx,ma[i][i+n-1]);
}
cout<<minn<<'\n'<<maxx;
return 0;
}4.凸多边形的划分
以边为划分，选 v0-v6这条边（为定边），找划分点k, 将多边形划分为两部分，【为什么要取v0-v6这条边呢，因为它是连接“首尾”的，这样一来，分成的俩部分就是v0v1v2v3和v3v4v5v6正好是顺序的，没有跨顺序的那种情况】然后再以分割边作“固定边”即对于左部分是v0v3, 右部分是v3v6接着进行每一个划分，直到划分为最小的三角形单元。（可以考虑如果我们以一个点固定的来划分，情况会很杂，划出的多边形情况不规范，不形成“子问题”）
AC代码：
//此题爆longlong不想用高精度所以用的__int128,但只能 “快读” 读入，所以也就学了一波快读 板子
//用了__int128就不能关同步流，否则超时。。
#include<iostream>
#include<algorithm>
using namespace std;
__int128 dp[60][60],a[60];
void read(__int128 &x){//也就是把平时的 ll数据类型改成了__int128(注意这个前面是两个下划线)
x=0;
int w=0; char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(w) x = -x;
}
void print(__int128 x){
if(x/10)print(x/10);
putchar(x%10+'0');
}
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++)read(a[i]);
for(int len=3;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
dp[i][j] = (__int128)5e28;
for(int k=i+1;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
}
}
print(dp[1][n]);
return 0;
}5.田忌赛马！
1.区间dp
（首先齐王是按从高到低的顺序出马）在田忌与齐王各自最强的马不战平的情况下，是可以贪心的：田忌当前最强的马比不过齐王当前最强的马时，就派出最弱的马去输，如果田忌的最强的马能赢，那就让这匹马去赢，【而没有必要说是找一匹能赢的中的最弱的马，因为齐王的是从高到低，田忌能赢齐王这匹马的最弱的马也一定能赢齐王的下一匹马，也即田忌派出了最强的马后，后面的马该赢的还是能赢，是没有影响的】
一旦他们最强的马战平
事情发生了逆转……会发现无论田忌是固定去找一匹最弱的输还是选择战平，都存在反例：如上图例子1，如果选择战平，就一分钱得不到，但如果选一匹最弱的（1）去输，后面就能赢两局（3对2，2对1）就能获得200金币；例子2：选最弱的2先去输3，后面3，再赢1，一分钱都得不到，但要是先战平，后面赢，就能获得200金币。–>>得出结论：战平时，具体出什么得看后面马的情况，无法单一地贪心
但是，我们发现，无论他们打不打平，田忌都是要么选一匹最强的马，要么选一匹最弱的马出去打，他选中间的一匹马出去是没有任何好处与优势的。然后听着就是由这个推出可以用dp来求最优解了（让我个菜鸡想 打死也不会啊www）
状态转移方程的推出：f[k][i][j]代表齐王派第k匹马时，田忌在区间 i~j中【实际上按策略只是选首尾第 i 或第 j 匹马】选马去战的最优金币数，所以，
f[k][i][j]=max(cal(i,k)+f[k+1][i+1][j], cal(j,k)+f[k+1][i][j-1])然后我们发现k, i, j 是存在数量关系的：k==1时，i =1，j=n; k==2时，i=1, j=n-1 或 i=2, j=n;……–> j – i == n – k ,注意的是它的原理，一开始的 [ i , j ] 区间是一整个1~n, 这个区间是田忌还没使用的马的区间，随着齐王派的马的增多，田忌可选的这个区间也在变短，同时这一定长的区间的位置是“不确定”的（因为还不知道他之前选的是 i 还是 j ）而到了最后一轮齐王派出第n匹马时，田忌派的这批马可以是[ 1，n ] 中的任意一匹，当区间长为1时，就可以直接与齐王的那批马计算f[i][i] 了
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e3+6;
int n,a[M],b[M],f[M][M];
int cal(int x,int y){
if(a[x]>b[y])return 200;
if(a[x]<b[y])return -200;
return 0;
}
int cmp(int x,int y){return x>y;}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for(int i=1;i<=n;i++)f[i][i]=cal(i,n);
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
int k=n-len+1;
f[i][j]=max(cal(i,k)+f[i+1][j],cal(j,k)+f[i][j-1]);
}
}
cout<<f[1][n];
return 0;
}2.贪心
（while里的两种判断想法都可以..注意别想错写错了qwq）
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e4+6;
int n,a[M],b[M],la,lb,ra,rb,ans;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
sort(a,a+n);
sort(b,b+n);
la=lb=0,ra=rb=n-1;
// while(la<=ra){
// if(a[ra]>b[rb]){
// ans+=200;
// ra--,rb--;
// }
// else if(a[ra]<b[rb]){
// ans-=200;
// la++;rb--;
// }
// else if(a[la]>b[lb]){//最差的能赢就先赢
// ans+=200;
// la++;lb++;
// }
// else{
// if(a[la]<b[rb])ans-=200;//注意是rb,输给齐王最好的马
// la++;rb--;
// }
// }
int ct=0;
while(ct<n){
if(a[ra]>b[rb]){
ans+=200;
ra--,rb--;
}
else if(a[la]>b[lb]){
ans+=200;
la++,lb++;
}
else if(a[la]<b[rb]){
ans-=200;
la++,rb--;
}
ct++;
}
cout<<ans;
return 0;
}6.两个定长度的不重叠子串最大和
这个题是我们学校出的捏~ 传送门
注意：长度到1e5了唉，简单两个for循环的dp会超时（亲身实践不说谎…）然后看到绝妙的优雅简洁代码，我一开始还觉得不对….我总觉得它（题解）代码里求的是两个紧挨着的串（因为我看着只觉得它在以一个分界点求其左右两边子串和）实际上分割点左边的最大子串和是用max记录了的，也就是说最大和不一定是要选取了分割点那个元素，而右子串和则是一定选取了分割点右边的那个元素，分割点又在合理范围内右移…绝妙。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=2e5+6;
int t,n,k;
ll a[M],ma,ans;
void solve(){
cin>>n>>k;
ans=ma=-1e18;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=k;i<=n-k;i++){
ma=max(ma,a[i]-a[i-k]);
ans=max(ans,ma+a[i+k]-a[i]);
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}