区间DP

区间DP与一般的线性DP的区别在于不知道起点从哪开始,因此只能以一个一个的区间划分,重要的就是区间的合并作为状态转移(与线段树有点像)...

模板题:

由于不知道从哪两堆石子开始合并,所以一般的线性DP解决不了。这个时候就要考虑区间DP了,可以用f[i][j]表示从编号为i的石子到编号为j的石子的最小得分.那么状态转移就很好想了,由两个石子的最小值相加

注意f[i][i]由于区间长度为一,并无分数所以应赋为0;

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
int n,w[maxn],f[maxn][maxn];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*ff;
}
inline void DP()
{
    for(int lenth=2;lenth<=n;lenth++)
    {
        for(int l=1;l<=n-lenth+1;l++)
        {
            int r=l+lenth-1;
            for(int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+w[r]-w[l-1]);
        }
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    memset(f,127,sizeof(f));
    n=read();
    for(int i=1;i<=n;i++) 
    {
        f[i][i]=0;
        w[i]=w[i-1]+read();
    }
    DP();
    cout<<f[1][n]<<endl;
    return 0;
}
View Code

由此可知道区间DP的一般适用范围。

下一题:

很明显与上一题的思路一样,添加括号使不同的两个集合的数成为一个数与合并的意义相似,用区间DP的一般解题思路相似,但这个题还要求输出方案,这个就要好好考虑.

一般鄙人用的方法就是递归,因为动态规划依据最优子原理求解问题,所以每个子结构都是最优的。

其次,应该想怎么根据结果推出方案数,我的方法就是根据状态转移推方案,例:本题的状态转移:for(int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);

既然f[l][r]是由k推出来,那我们也就可以枚举k,找到符合条件的f[l][k]与f[k+1][r]值使其符合f[l][i]+f[i+1][r]+sum[r]-sum[l-1]==v,此时的k就是转移时的k值,这样便可轻易知道方案了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define _ 0
const int maxn=30;
int f[maxn][maxn],n,a[maxn],sum[maxn];//f[i][j]表示从i到j合并的最大值;
int ans[maxn],o,sum2[maxn];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*ff;
} 
inline void put(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) put(x/10);
    putchar(x%10+'0');
}
inline void DP()
{
    memset(f,10,sizeof(f));
    for(int i=1;i<=n;i++) f[i][i]=0;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l<=n-len+1;l++)
        {
            int r=l+len-1;
            for(int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
        }
    }
}
inline void find1(int l,int r,int v)
{
    if(l==r)
    {
        put(a[l]);
        return;
    }
    putchar('(');
    if(r-l==1)
    {    
        put(a[l]);putchar('+');put(a[r]);
        ans[++o]=sum[r]-sum[l-1];
        putchar(')');
        return;
    } 
    for(int i=r;i>=l;i--)
    {
        if(f[l][i]+f[i+1][r]+sum[r]-sum[l-1]==v)
        {
            find1(l,i,v-(sum[r]-sum[l-1])-f[i+1][r]);
            putchar('+');
            find1(i+1,r,v-(sum[r]-sum[l-1])-f[l][i]); 
            break;
        }
    }    
    ans[++o]=sum[r]-sum[l-1];
    putchar(')');
}
int main()
{
    freopen("1.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];
    DP();
    find1(1,n,f[1][n]);
    cout<<endl;
    put(f[1][n]);
    cout<<endl;
    for(int i=1;i<=o;i++) put(ans[i]),putchar(' '); 
    return (0^_^0);
}
View Code
原文地址:https://www.cnblogs.com/gcfer/p/10637659.html