HihoCoder 1636

/**

 * 题目链接：https://cn.vjudge.net/problem/HihoCoder-1636

 * 题目意思，石子合并，每次可以合并相邻的石子。每次可以x堆合并为一堆。

 * x属于[l,r] 的闭区间。问最小花费。

 *

 * 思路：dp[i][j][k] 代表 区间i～j这个区间目前有k堆的最小花费；

 * 那么一开始 dp[i][j][j-i+1]=0;

 * 转移方程： dp[i][j][k]=min(dp[i][p][k-1]+dp[p+1][j][1]);

 * 如果k在l到r范围可以还有合并，合并转移方程： dp[i][j][1]=min(dp[i][j][k]+sum[i][j]);

 * sum[i][j],代表区间i～j的区间和。

 *

 * 疑问 转移方程为什么是：dp[i][j][k]=min(dp[i][p][k-1]+dp[p+1][j][1]);

 * 而不是：dp[i][j][k]=min(dp[i][p][x]+dp[p+1][j][k-x]);

 * 因为 dp[i][j][k] 由 dp[i][p][x]+dp[p+1][j][k-x] 等效于 dp[i][pp][k-1]+dp[pp+1][j][1]

 * 故可以这样写。

 **/

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

typedef long long int LL;

const int INF=0x3f3f3f3f;

const int maxn=108;

int n,l,r,a[maxn];

int dp[maxn][maxn][maxn] ,sum[maxn][maxn];

int main()

{

    while(scanf("%d%d%d",&n,&l,&r)+1)

    {

        memset(dp,0x3f,sizeof(dp));

        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

        for(int i=1;i<=n;i++)

        {

            sum[i][i-1]=0;

            for(int j=i;j<=n;j++) sum[i][j]=sum[i][j-1]+a[j];

        }

        for(int i=1;i<=n;i++)

        {

            for(int j=i;j<=n;j++)

            {

                dp[i][j][j-i+1]=0;

            }

        }

        for (int len = 2; len <= n; len++)

        {

            for (int i = 1, j = i + len - 1; j <= n; i++, j++)

            {

                for (int p = i; p < j; p++)

                {

                    for(int k=1;k<=len;k++)

                    {

                        dp[i][j][k]=min(dp[i][j][k],dp[i][p][k-1]+dp[p+1][j][1]);

                        if(l<=k&&k<=r) dp[i][j][1]=min(dp[i][j][1],dp[i][j][k]+sum[i][j]);

                    }

                }

            }

        }

        int ans=dp[1][n][1];

        if(ans>=INF) ans=0;

        printf("%d\n",ans);

    }

    return 0;

}

/*

3 2 2

1 2 3

3 2 3

1 2 3

4 3 3

1 2 3 4

2 1 1

1 2

*/
巴特西

HihoCoder 1636

最新文章

热门文章
