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

ゞ浴缸里的玫瑰 2022-09-18 13:56 190阅读 0赞

## 整数划分（四） ##

链接： [http://acm.nyist.net/JudgeOnline/problem.php?pid=746][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][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;
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_746]: http://acm.nyist.net/JudgeOnline/problem.php?pid=746
[http_acm.nyist.net_JudgeOnline_problem.php_pid_737]: http://acm.nyist.net/JudgeOnline/problem.php?pid=737