被按着打
区间DP
这个应该是最基础的吧
从小阶段推到大的阶段
P1880 [NOI1995] 石子合并
经典题，一个trick是破环为链
贴个代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
int dp[N][N][2],a[N],n,s[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i],a[i+n]=a[i];
int n1=n<<1;
for(int i=1;i<=n1;++i)
for(int j=1;j<=n1;++j) dp[i][j][1]=2e9;
for(int i=1;i<=n1;++i) dp[i][i][0]=dp[i][i][1]=0,s[i]=s[i-1]+a[i];
for(int len=2;len<=n;++len)
for(int l=1,r=l+len-1;r<=n1;++l,++r)
for(int k=l;k<r;++k)
dp[l][r][0]=max(dp[l][r][0],dp[l][k][0]+dp[k+1][r][0]+s[r]-s[l-1]),
dp[l][r][1]=min(dp[l][r][1],dp[l][k][1]+dp[k+1][r][1]+s[r]-s[l-1]);
int ans1=0,ans2=2e9;
for(int i=1;i<=n;++i)
ans1=max(dp[i][i+n-1][0],ans1),
ans2=min(dp[i][i+n-1][1],ans2);
cout<<ans2<<endl<<ans1<<endl;
}
能量项链
我们枚举此刻的长度，再进行转移就行了
方程是\(dp[i][j]=\max\limits_{i<k<j}{(dp[i][k]+dp[k][j]+a[i]\cdot a[k] \cdot a[j])}\)
P1040 [NOIP2003 提高组] 加分二叉树
由于中序遍历一定，可枚举子树根节点，转化为区间DP
这道题让我们记录最佳的状态，转移时记录即可
方程好写 Latex不好写
\(f[i][j]=\max\limits_{i<k<j}(f[i][k-1]\cdot f[k+1][j]+a[k])\)
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
const int N=35;
int dp[N][N],n;
int root[N][N];
int a[N];
void pr(int l,int r)
{
if(l>r) return;
cout<<root[l][r]<<" ";
pr(l,root[l][r]-1);
pr(root[l][r]+1,r);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(re int i=1;i<=n;++i) cin>>a[i];
for(re int len=1;len<=n;++len)
{
for(re int l=1;l<=n-len+1;++l)
{
int r=l+len-1;
dp[l][r]=max(dp[l+1][r]+a[l],dp[l][r-1]+a[r]);
root[l][r]=(dp[l+1][r]+a[l]==dp[l][r])?l:r;
for(re int k=l+1;k<r;++k)
{
if(dp[l][k-1]*dp[k+1][r]+a[k]>dp[l][r])
{
dp[l][r]=dp[l][k-1]*dp[k+1][r]+a[k];
root[l][r]=k;
}
}
}
}
cout<<dp[1][n]<<endl;
pr(1,n);
}
P1436 棋盘分割
二维区间DP
同理，枚举两个维度的长度，转移较容易,用二维前缀和优化
#include<bits/stdc++.h>
using namespace std;
const int N=16,V=8;
int n,a[N][N],val[N][N],dp[9][9][9][9][N];
inline int ask(int a,int b,int c,int d)
{
return val[c][d]+val[a-1][b-1]-val[a-1][d]-val[c][b-1];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n,--n;
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=V;++i)
for(int j=1;j<=V;++j)
cin>>a[i][j],val[i][j]=val[i][j-1]+val[i-1][j]-val[i-1][j-1]+a[i][j];
for(int i=1;i<=V;++i)
for(int j=1;j<=V;++j)
for(int p=i;p<=V;++p)
for(int q=j;q<=V;++q)
dp[i][j][p][q][0]=ask(i,j,p,q)*ask(i,j,p,q);
for(int xlen=1;xlen<=V;++xlen)
for(int ylen=1;ylen<=V;++ylen)
for(int xl=1,xr=xl+xlen-1;xr<=V;++xr,++xl)
for(int yl=1,yr=yl+ylen-1;yr<=V;++yr,++yl)
{
for(int p=xl;p<xr;++p)
for(int k=1;k<=n;++k)
dp[xl][yl][xr][yr][k]=min(dp[xl][yl][xr][yr][k],min(dp[xl][yl][p][yr][k-1]+dp[p+1][yl][xr][yr][0],dp[xl][yl][p][yr][0]+dp[p+1][yl][xr][yr][k-1]));
for(int p=yl;p<yr;++p)
for(int k=1;k<=n;++k)
dp[xl][yl][xr][yr][k]=min(dp[xl][yl][xr][yr][k],min(dp[xl][yl][xr][p][0]+dp[xl][p+1][xr][yr][k-1],dp[xl][yl][xr][p][k-1]+dp[xl][p+1][xr][yr][0]));
}
cout<<dp[1][1][V][V][n];
}
树形DP
可以看看这篇blog，讲的挺好
#10155 数字转换
我们对每个点，他的约数和和自己中，小的往大的连边（若相同便不管）
然后会形成森林，我们要做的就是求所有树中最大的直径
代码找不到了
P2015 二叉苹果树
书上背包板子
#include<bits/stdc++.h>
#define register
#define int long long
using namespace std;
const int N=105,NN=1e4+5;
int to[NN],ne[NN],f[N],tot,e[NN];
int dp[N][N];
int n,m;
inline void add(int x,int y,int z){to[++tot]=y,e[tot]=z,ne[tot]=f[x],f[x]=tot;}
inline void dp1(int x,int fa)
{
for(int y,i=f[x];i;i=ne[i])
{
if((y=to[i])==fa) continue;
dp1(y,x);
for(int j=m;j;--j)
for(int k=j-1;~k;--k) dp[x][j]=max(dp[x][j],dp[x][j-1-k]+e[i]+dp[y][k]);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int x,y,z;
for(int i=1;i<n;++i) cin>>x>>y>>z,add(x,y,z),add(y,x,z);
dp1(1,0);
cout<<dp[1][m];
}