区间dp
先在小区间上进行dp得到最优解，然后再合并小区间的最优解求得大区间的最优解，解题时，先解决小区间的问题，再将小区间合并为大区间，合并操作一般是将两个相邻区间合并
注：合并顺序从小区间到大区间，因该先从小到大枚举区间的长度，递推出j在哪里
一本通题解
T4：
啊啊啊为什么区间dp的题想根本想不出来啊啊啊
设 \(dp[i][j]\) 表示区间获得的最大价值是多少（注：不是将区间内全部删掉）
我们分情况讨论
考虑如果 \((i+1,j-1)\) 这段区间可以全部被删除，就考虑能不能将 \((i,j)\) 合并删除掉
如何判断 \((i+1,j-1)\) 这段区间可以全部被删除是否成立？
只要满足条件 \(dp[i+1][j-1]==\sum_{i=i+1}^{r-1} b[i]\) 即可（因为这一段可以全部删掉就自然可以获得这一段的价值总和）
因为正常的合并条件为 \(a[i]+a[j]<=k\)，所以再次判断一下即可
如果 \((i+1,j-1)\) 这段区间不可以全部被删除
我们自然是将大区间拆分小区间的方法，就是正常区间dp做法，枚举断点k即可
T5：
推式子。。。
求最小值，经典操作，先把固定的东西丢掉
去掉根号
考虑用二维区间dp实现
这里有一点变式，因为这个不是从小区间推导到大区间，而是从前一次的状态推导到这一次，并不需要区间从小到大枚举，但是我们是倒推，从一个小矩形往边上加块，推得一个大区间，所以我们要把那些不合法还没有通过推导得到的状态设为inf
\(dp[i][j][x][y][k]\) 代表第k次转移，合并出来的块左上角为 \((i,j)\) 右下角为 \((x,y)\) 的最小代价，所以初始状态就是使 \(dp[i][j][x][y][0]\) 为这个块的权值，也可以理解为最后剩下来的块的大小
转移
这个是横着割竖着割不同的情况，枚举g，我们可以分别选择一个块s作为我们拼出来的块，另一个块t代表我们此次操作拼上去的块，所以本次的贡献既是 \(dp[s][k-1]+num[t]\) （num代表块的权值和）
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int a[N][N],num[N][N],sum[N][N],dp[N][N][N][N][20];
int query(int i,int j,int x,int y){
int cnt=sum[x][y]+sum[i-1][j-1]-sum[i-1][y]-sum[x][j-1];
return cnt*cnt;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
scanf("%d",&a[i][j]);
num[i][j]=num[i][j-1]+a[i][j];
sum[i][j]=sum[i-1][j]+num[i][j];
}
}
memset(dp,0x3f3f3f,sizeof(dp));
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
for(int x=i;x<=8;x++){
for(int y=j;y<=8;y++){
dp[i][j][x][y][0]=query(i,j,x,y);
}
}
}
}
for(int k=1;k<n;k++){
for(int lenx=1;lenx<=8;lenx++){
for(int i=1;i+lenx-1<=8;i++){
for(int leny=1;leny<=8;leny++){
for(int j=1;j+leny-1<=8;j++){
int x=i+lenx-1,y=j+leny-1;
for(int g=i;g<x;g++){
dp[i][j][x][y][k]=min(dp[i][j][g][y][k-1]+query(g+1,j,x,y),dp[i][j][x][y][k]);
dp[i][j][x][y][k]=min(dp[g+1][j][x][y][k-1]+query(i,j,g,y),dp[i][j][x][y][k]);
}
for(int g=j;g<y;g++){
dp[i][j][x][y][k]=min(dp[i][j][x][g][k-1]+query(i,g+1,x,y),dp[i][j][x][y][k]);
dp[i][j][x][y][k]=min(dp[i][g+1][x][y][k-1]+query(i,j,x,g),dp[i][j][x][y][k]);
}
}
}
}
}
}
double xb=(double)sum[8][8]/(double)n;
// printf("%lf\n",xb);
printf("%.3lf",sqrt((double)dp[1][1][8][8][n-1]/(double)n-xb*xb));
}
T6：
为什么这么简单的题我都想不出来！！！
只能从两边删数可以看成从一个中心区间拓展到两个大区间的过程
我们可以对于区间 \((i,j)\) 分为两种情况
1.直接删去区间
2.分别删去
枚举k，正常转移即可
T7：
差一点就想到了啊啊啊啊啊啊啊
没有想起来区间dp要枚举k呜呜呜
贪心策略：
最有情况下，必定将一个狼一次性消灭，证明因为把一只狼消灭到一半再去攻击其他的狼受到伤害必定不小于一次性消灭掉的伤害
我们设 \(dp[i][j]\) 为删去 \((i,j)\) 受到伤害最小值
于是只要枚举攻击的狼k，受到的伤害为 \((b[i-1]+b[j+1]+a[k])*c[i]\) （\(c[i]\) 为受到攻击的次数）
转移式子
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+(a[k]+b[i-1]+b[j+1])*h[k]);
}
注意初始化时要把所有状态设为inf
然后对于 \(dp[i][i]=(a[i]+b[i-1]+b[i+1])*c[i]\)
注意因为我的代码还有一点比较特殊就是会访问到 \(dp[i+1][i],dp[i][i-1]\) 所以将这些赋值为0即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=405;
int n,atk;
int a[N],b[N],h[N],dp[N][N];
int main(){
scanf("%d%d",&n,&atk);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i],&b[i],&h[i]);
h[i]=(int)ceil((double)h[i]/(double)(atk));
}
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int len=1;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(len==1){
dp[i][j]=(a[i]+b[i-1]+b[i+1])*h[i];
dp[i][i-1]=dp[i+1][i]=0;
continue;
}
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+(a[k]+b[i-1]+b[j+1])*h[k]);
}
}
}
printf("%d",dp[1][n]);
}
T8：
我们把一整块都为白色的贡献设为0，否则设为 \(\max(n,m)\)
然后二维区间dp转移即可
T9：
设 \(dp[i][j]\) 为男生选i，女生选j，所获取到的最大愉悦度，至于为什么这个dp没有后效性。。。我也不知道。。。
然后我们可以枚举上一维是由选哪两个人，得来的，可以枚举不选前一段男生或不选前一段女生的长度，具体转移式子可以参考ybt
这里为什么可以只枚举删去一段连续的女生或男生而不是两边都删呢，我们会发现这因该是包不优的，因为我们可以在两边都不选的一堆男生和女生中插进来一对，一定比之前更优
这里我之前有一个问题，就是这里为什么要选取边界条件设为-inf呢
for(int i=1;i<=n+1;i++){
dp[i][0]=dp[0][i]=-inf;
}
考虑首先在定义上它就不合法， \((0,0)\) 一定要配成一对，然后第0号男生女生就不可以再配对其余男生或女生了，其次，如果说它可以这样转移的话，会有一部分算不上贡献，如下
最终代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=305,inf=1e18+5;
int n;
int a[N],suma[N],sumb[N],b[N],dp[N][N];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
suma[i]=suma[i-1]+a[i];
}
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
sumb[i]=sumb[i-1]+b[i];
}
suma[n+1]=suma[n];
sumb[n+1]=sumb[n];
for(int i=1;i<=n+1;i++){
dp[i][0]=dp[0][i]=-inf;
}
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+1;j++){
dp[i][j]=dp[i-1][j-1]+a[i]*b[j];
for(int k=1;k<i;k++){
dp[i][j]=max(dp[k-1][j-1]+a[i]*b[j]-(suma[i-1]-suma[k-1])*(suma[i-1]-suma[k-1]),dp[i][j]);
}
for(int k=1;k<j;k++){
dp[i][j]=max(dp[i-1][k-1]+a[i]*b[j]-(sumb[j-1]-sumb[k-1])*(sumb[j-1]-sumb[k-1]),dp[i][j]);
}
}
}
printf("%lld",dp[n+1][n+1]);
}