P1880 NOI1995石子合并


继续重新学dp,当年写的代码真是丑,一点缩进都没有…

基本区间dp,由于是环形,先复制一份然后继续求解,可以发现区间长度可以递增,把它作为状态,之后枚举左端点,求出右端点,然后在这中间枚举端点,进行更新。之后在扫一遍去最优就好了

#include<bits/stdc++.h>
using namespace std;
const int maxn=300;
const int inf=0x3f3f3f3f;
int n,a[maxn],f[maxn][maxn],sum[maxn],g[maxn][maxn];
int ans1=0x3f3f3f3f,ans2=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*n;j++) f[i][j]=inf,g[i][j]=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) a[i+n]=a[i];
    for(int i=1;i<=2*n;i++)
    {
        f[i][i]=0;
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;len++)
        for(int l=1;l<=2*n-len+1;l++)
        {
            int r=l+len-1;
            for(int k=l;k<=r-1;k++) 
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
                g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]);
            }
            f[l][r]+=sum[r]-sum[l-1];
            g[l][r]+=sum[r]-sum[l-1];
        }
    for(int l=1;l<=n;l++) 
    {
        ans1=min(ans1,f[l][l+n-1]);
        ans2=max(ans2,g[l][l+n-1]);
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P2014 选课 P2014 选课
这是树上背包型问题 $f[i][j]$表示对于以$i$为根的子树中选$j$个获得的学分 则有$f[i][j]=min(f[i][j-k-1]+f[v][k]+w[v])$ 之所以$j-k-1$是因为子树中肯定要取$v$,对于每一个子树,都进
2019-07-06
下一篇 
tyvj1061 Mobile Service tyvj1061 Mobile Service
线性dp,注意初始化以及三个点不能相同,还有不要弱智爆内存 #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; int l,n,c[50
2019-07-06
  目录