区间dp（整数划分，石子划分）-蒲公英云

区间dp（整数划分，石子划分）

整数划分（四）

链接： http://acm.nyist.net/JudgeOnline/problem.php?pid=746

基础区间dp，代码：

#include <cstdio>
#include <cstring>
long long a[20][20];
long long dp[25][25];
int main()
{
    int T,m;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        char s[22];
        scanf("%s",s+1);
        scanf("%d",&m);
        int l=strlen(s),ok=1;
        memset(a,0,sizeof(a));
        for(int i=1;i<l;i++)
        {
            if(s[i]=='0')
                ok=0;
            for(int j=i;j<l;j++)
            {
                a[i][j]=a[i][j-1]*10+(s[j]-'0');
            }
        }
        if(ok==0&&l-1==m||l-1<m)
        {
            printf("0\n");continue;
        }
        long long x,ans;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<l;i++)
            dp[i][1]=a[1][i];
        ans=0;
        if(m==1)
            ans=dp[l-1][1];
        for(int j=2;j<=m;j++)
        {
            for(int i=j;i<l;i++)
            {
                ans=a[i][i];
                for(int k=1;k<i;k++)
                {
                    x=dp[k][j-1]*a[k+1][i];
                    if(x>ans)
                        ans=x;
                }
                dp[i][j]=ans;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

石子合并（一）

链接： http://acm.nyist.net/JudgeOnline/problem.php?pid=737

代码：

#include <cstdio>
#include <cstring>
#define N 210
int dp[N][N],sum[N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int a[N];sum[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        memset(dp,0,sizeof(dp));
        int i,j,l,k;
        for(l = 2; l <= n; ++l)
        {
            for(i = 1; i <= n - l + 1; ++i)
            {
                j = i + l - 1;
                dp[i][j] = 2100000000;
                for(k = i; k < j; ++k)
                {
                    int q = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1];
                    if(dp[i][j] > q)
                        dp[i][j] = q;
                }
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}