Pangu and Stones(HihoCoder-1636)(17北京OL)【区间DP】

题意：有n堆石头，盘古每次可以选择连续的x堆合并，所需时间为x堆石头的数量之和，x∈[l,r],现在要求，能否将石头合并成一堆，如果能，最短时间是多少。

思路：（参考了ACM算法日常）DP[i][j][k],表示当前状态下[i,j]这个区间分成了k堆。

　　　状态转移：1.k=1时，dp[i][j][k]=min(dp[i][j][D]+num[j]-num[i-1]),其中D∈[l,r],

　　　　　　　　2.k!=1时，dp[i][j][k]=min(dp[i][z][1]+dp[z+1][j][k-1]),（合并成k堆时，可以转化为k-1堆与1堆合并，此时就是区间DP的思路了）

代码如下：

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int n,l,r,a[];

int dp[][][],num[];

int main(){

    while(~scanf("%d%d%d",&n,&l,&r)){

        num[]=;

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

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

            scanf("%d",&a[i]);

            num[i]=num[i-]+a[i];

        }

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

            dp[i][i][]=;

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

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

                for(int k=i;k>=;k--){

                    if(k==){

                        for(int z=l;z<=r;z++)

                        dp[j][j+i-][k]=min(dp[j][j+i-][k],dp[j][j+i-][z]+num[j+i-]-num[j-]);

                    }

                    else {

                        for(int z=j;z<j+i-;z++)

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

                    }

                }

            }

        }

        if(dp[][n][]==0x3f3f3f3f)

            printf("0\n");

        else printf("%d\n",dp[][n][]);

    }

    return ;

}

By xxmlala

巴特西

Pangu and Stones(HihoCoder-1636)(17北京OL)【区间DP】

最新文章

热门文章