dp总结
p1005 矩阵取数游戏
因为每行之间结果相互独立，所以可以单独对每行算，考虑每行进行dp，
状态：dp[i][j]表示从前面选了i个数，后面选了j个数的最大值
转移：(f[i][j]=max(f[i-1][j]+a[k][i]*ksm(2,i+j),f[i][j-1]+a[k][m-j+1]*ksm(2,i+j))) ;
注意此题需要高精；
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110;
__int128 n,m,ans,sum;
__int128 a[N][N],f[N][N];
inline __int128 read() {
__int128 s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
__int128 ksm(__int128 a,__int128 b){
__int128 res=1;
for(;b;b>>=1){
if(b&1) res=res*a;
a=a*a;
}
return res;
}
void put(__int128 x){
if(x>9){
put(x/10);
}
cout<<(int)(x%10);
}
int main(){
n=read(); m=read();
// cout<<ksm(2,m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=read();
}
}
for(int k=1;k<=n;k++){
memset(f,0,sizeof(f));
sum=0;
f[1][0]=2*a[k][1];
f[0][1]=2*a[k][m];
// cout<<f[0][1]<<"
";
// cout<<f[1][0]<<"
";
for(int i=0;i<=m;i++){
for(int j=0;j<=m&&j+i<=m;j++){
if(!i&&!j) continue;
if(i-1<0) f[i][j]=f[i][j-1]+a[k][m-j+1]*ksm(2,i+j);
else if(j-1<0) f[i][j]=f[i-1][j]+a[k][i]*ksm(2,i+j);
else f[i][j]=max(f[i-1][j]+a[k][i]*ksm(2,i+j),f[i][j-1]+a[k][m-j+1]*ksm(2,i+j));
// cout<<f[i-1][j]<<" "<<f[i][j-1]<<" "<<i<<" "<<j<<" "<<f[i][j]<<"
";
if(i+j==m) sum=max(sum,f[i][j]);
}
}
// cout<<sum<<"
";
ans+=sum;
}
put(ans);
return int(0);
}
能量项链
一道经典的环形区间DP
对于非环形的区间DP，常规做法是dp[l][r]计算l~r这一段合并的最大价值
在枚举分割点，转移O(n)的情况下，这一做法拥有O(n^3)的时间复杂度
在环形的情况下，一个不优秀的做法是，枚举一个分割点，把环分割成一条链做区间DP，使得复杂度生生来到 O(n^4)
实际上，对于环形区间DP，常用的状态是dp[i][len]计算从i往后推len个位置的一段合并的最大价值
DP顺序按len从小往大即可
子串
匹配dp问题；
状态：f[i][j][k][0/1]表示A串前i位，选了k个子串，与b串前位匹配的方案数；
若A[i]!=b[i] f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1];
若A[i]==b[j] 分三种情况：
1，A[i]不加入子串，f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1];
2，A[i]加入前一个子串中 f[i][j][k][1]=f[i-1][j-1][k][1];
3,A[i]新开一个子串 f[i][j][k][1]=f[i-1][j-1][k-1][1]+f[i-1][j-1][k-1][0];
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int p=1e9+7;
int n,m,t,s;
long long f[3][210][1010][3];
char a[1010],b[210];
int main(){
scanf("%d%d%d",&n,&m,&t);
scanf("%s",a+1);
scanf("%s",b+1);
int now=1;
// f[0][0][0][0]=1;
for(int i=1;i<=n;i++){
now^=1;
f[now][1][1][0]=s;
if(a[i]==b[1]) f[now][1][1][1]=1,s++;
for(int j=2;j<=m;j++){
for(int k=1;k<=t;k++){
if(a[i]!=b[j]) f[now][j][k][0]=1LL*(1LL*f[now^1][j][k][0]+f[now^1][j][k][1])%p;
else{
f[now][j][k][0]=1LL*(1LL*f[now^1][j][k][0]+f[now^1][j][k][1])%p;
f[now][j][k][1]=1LL*(1LL*(1LL*f[now^1][j-1][k-1][0]+f[now^1][j-1][k-1][1])%p+f[now^1][j-1][k][1])%p;
}
}
}
for(int j=1;j<=m;j++){
for(int k=1;k<=t;k++){
f[now^1][j][k][0]=f[now^1][j][k][1]=0;
}
}
}
cout<<1LL*(f[now][m][t][0]+f[now][m][t][1])%p;
}
换教室
状态很好设 f[i][j][1/0]表示前i个课程，已经换了j次，第i次换/没换的方案数；
(f[i][j][0]=min(f[i-1][j][0]+dis[a[i-1]][a[i]],f[i-1][j][1]+k[i-1]*dis[b[i-1]][a[i]]+(1-k[i-1])*dis[a[i-1]][a[i]]);)
(f[i][j][1]=min(f[i-1][j-1][0]+(1-k[i])*dis[a[i-1]][a[i]]+k[i]*dis[a[i-1]][b[i]],f[i-1][j-1][1]+k[i-1]*(k[i]*dis[b[i-1]][b[i]]+(1-k[i])*dis[b[i-1]][a[i]]))
(+(1-k[i-1])*(k[i]*dis[a[i-1]][b[i]]+(1-k[i])*dis[a[i-1]][a[i]]));)
分两种情况
第i-1个选或不选；
算出概率及期望，3层for循环算出任意两点间距离；
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e3+7;
int n,m,v,e;
int a[N],b[N],dis[310][310];
double k[N];
double f[N][N][3];
int main(){
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
for(int i=1;i<=n;i++){
scanf("%lf",&k[i]);
}
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=v;i++){
dis[i][i]=0;
}
for(int i=1;i<=e;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
dis[x][y]=dis[y][x]=min(dis[x][y],z);
}
for(int k=1;k<=v;k++){
for(int i=1;i<=v;i++){
for(int j=1;j<=v;j++){
if(i!=j&&i!=k&&k!=j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
memset(f,0x7f,sizeof(f));
f[1][0][0]=f[1][1][1]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=min(i,m);j++){
f[i][j][0]=min(f[i-1][j][0]+dis[a[i-1]][a[i]],f[i-1][j][1]+k[i-1]*dis[b[i-1]][a[i]]+(1-k[i-1])*dis[a[i-1]][a[i]]);
if(j!=0)f[i][j][1]=min(f[i-1][j-1][0]+(1-k[i])*dis[a[i-1]][a[i]]+k[i]*dis[a[i-1]][b[i]],f[i-1][j-1][1]+k[i-1]*(k[i]*dis[b[i-1]][b[i]]+(1-k[i])*dis[b[i-1]][a[i]])+(1-k[i-1])*(k[i]*dis[a[i-1]][b[i]]+(1-k[i])*dis[a[i-1]][a[i]]));
}
}
double ans=33333333;
for(int i=0;i<=m;i++) ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%.2f",ans);
}