区间dp学习
区间dp
拆分型
将dp拆分为几个子区间，分别求解子问题，再通过合并子问题来解决大问题
P1775
顺便作为模版讲解，定义dp[l][r]为合并l到r的最小代价，为了得到区间，我们需要枚举l和长度来枚举r,然后设置分割点k将区间拆分为两个区间，最后算出代价的状态转移方程
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
#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
#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，注意状态转移方程为
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;
}#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
每个零食都可以卖以前的或者以后的，所以要把这两种情况都加上，然后公式化枚举起点和长度就行，注意状态转移方程内需要×持有天数
#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
对于每个点，我们选择这个点左边的人
对于这个人选择左边
dp[l][r][0]+=dp[l+1][r][0]%mod;选择右边
dp[l][r][0]+=dp[l+1][r][1]%mod;然后选这个点右边的人 对于这个人选择左边
dp[l][r][1]=(dp[l][r][1]%mod+dp[l][r-1][0]%mod)%mod;选择右边
dp[l][r][1]=((dp[l][r][1]%mod+dp[l][r-1][1]%mod)+mod)%mod;
最后输出答案dp[1][n][0]+dp[1][n][1];```
#include<bits/stdc++.h>
using namespace std;
#define mod 19650827
const int maxn = 2e3+7;
int a[maxn];
int dp[maxn][maxn][2];
int main() {
int n;
cin>>n;
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++) {
cin>>a[i];
dp[i][i][0]=1,dp[i][i][1]=0;
}
for(int len=2; len<=n; len++) {
for(int l=1; l+len-1<=n; l++) {
int r=len+l-1;
if(a[l]<a[l+1]) {
dp[l][r][0]+=dp[l+1][r][0]%mod;
}
if(a[l]<a[r]) {
dp[l][r][0]+=dp[l+1][r][1]%mod;
}
if(a[l]<a[r]) {
dp[l][r][1]=(dp[l][r][1]%mod+dp[l][r-1][0]%mod)%mod;
}
if(a[r-1]<a[r]) {
}
dp[l][r][1]%=mod;
dp[l][r][0]%=mod;
}
}
cout<<(dp[1][n][1]+dp[1][n][0])%mod;
return 0;
}