区间dp

拆分型

将dp拆分为几个子区间，分别求解子问题，再通过合并子问题来解决大问题

P1775

顺便作为模版讲解，定义dp[l][r]为合并l到r的最小代价，为了得到区间，我们需要枚举l和长度来枚举r,然后设置分割点k将区间拆分为两个区间，最后算出代价的状态转移方程

CPP

dp[l][r]=min(dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1],dp[l][r]);

注意边界和起始值，要不影响答案，自己到自己距离为0，所以需要给dp数组极大值，然后dp[i][i]=0

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e2+7;
int a[maxn],sum[maxn];
int dp[maxn][maxn];
int main() {
	int n;
	cin>>n;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		dp[i][i]=0;
	}
	for(int len=1;len<=n;len++) {
		for(int l=1;l+len-1<=n;l++){
			int r=len+l-1;
			for(int k=l;k<r;k++) {
				dp[l][r]=min(dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1],dp[l][r]);
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}

P1622

和上一题类似，将牢房分割成q个区间，然后使用结构体存储每一个区间的l和r，然后向上一题一样设分割点，最后得出合并代价a[r].r-a[l].l

CPP

#include<bits/stdc++.h>
using namespace std;
int p,q;
const int maxn = 1e3+6;
struct Node{
	int l,r;
}a[maxn];
int dp[maxn][maxn];
int main() {
	cin>>p>>q;
	a[0].r=-1;
	for(int i=1;i<=q;i++) {
		int x;
		cin>>x;
		a[i].l=a[i-1].r+2;
		a[i].r=x-1;
	}
	a[q+1].l=a[q].r+2;
	a[q+1].r=p;
	int n=q+1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			dp[i][j]=INT_MAX;
			dp[i][i]=0;
		}
	}
	for(int len=2;len<=n;len++) {
		for(int l=1;l+len-1<=n;l++) {
			int r=l+len-1;
			for(int k=l;k<r;k++) {
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+a[r].r-a[l].l);
			}
		}
	}
	cout<<dp[1][q+1];
	return 0;
}

UVA348

要求我们给出格式
首先对于输出，我们可以把字符串看做左右儿子，用中序遍历完成字符串输出
注意枚举长度从2开始一直到n，然后套模版枚举l和len，注意状态转移方程为

CPP

if(dp[l][k]+dp[k+1][r]+q[l].n*q[k].m*q[r].m<dp[l][r]) {
						dp[l][r]=dp[l][k]+dp[k+1][r]+q[l].n*q[k].m*q[r].m;
						d[l][r]=k;
					}

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 11;
struct Q {
	int n,m;
} q[maxn];
int dp[maxn][maxn];
int d[maxn][maxn];
void print(int l,int r)  {
	if(l==r) {
		cout<<"A"<<l;
		return;
	}
	int k=d[l][r];
	cout<<"(";
	print(l,k);
	cout<<" x ";
	print(k+1,r);
	cout<<")";
	return ;
}
int n;
int cnt;
int main() {
	while(cin>>n&&n) {
		cnt++;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				dp[i][j]=1e9;
			}
		}
		for(int i=1; i<=n; i++) {
			dp[i][i]=0;
		}
		for(int i=1; i<=n; i++) {
			cin>>q[i].n>>q[i].m;
		}
		for(int len=2;len<=n;len++) {
			for(int l=1;l+len-1<=n;l++) {
				int r=l+len-1;
				for(int k=l;k<=r;k++) {
					if(dp[l][k]+dp[k+1][r]+q[l].n*q[k].m*q[r].m<dp[l][r]) {
						dp[l][r]=dp[l][k]+dp[k+1][r]+q[l].n*q[k].m*q[r].m;
						d[l][r]=k;
					}
				}
			}
		}
		cout<<"Case "<<cnt<<": ";
		print(1,n);
		cout<<"\n";
	}
	return 0;
}

两端扩展性

一般这种问题有个方向可以选择，于是我们这两种方案都要计算最后在整合

P2858

每个零食都可以卖以前的或者以后的，所以要把这两种情况都加上，然后公式化枚举起点和长度就行，注意状态转移方程内需要×持有天数

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+7;
int a[maxn];
int dp[maxn][maxn];
int main() {
	int n;
	cin>>n;
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		dp[i][i]=a[i]*n;
	}
	for(int len=2; len<=n; len++) {
		for(int l=1; l+len-1<=n; l++) {
			int r=len+l-1;
			dp[l][r]=max(dp[l][r],max(dp[l+1][r]+a[l]*(n-r+l),dp[l][r-1]+a[r]*(n-r+l)));
		}
	}
	cout<<dp[1][n];
	return 0;
}

P3205

对于每个点，我们选择这个点左边的人
对于这个人选择左边

CPP

dp[l][r][0]+=dp[l+1][r][0]%mod;

选择右边

CPP

dp[l][r][0]+=dp[l+1][r][1]%mod;

然后选这个点右边的人对于这个人选择左边

CPP

dp[l][r][1]=(dp[l][r][1]%mod+dp[l][r-1][0]%mod)%mod;