uva 10003 动态规划

待我称王封你为后i 2022-08-03 13:41 10阅读 0赞

给定一个长度为len的木板，要在n个位置处切开，每次切开的代价是这块木板的长度，求最小的代价。

其实切木板跟合并木板是等价的。。

开始以为是简单的贪心，便写了一个优先队列的贪心算法，果断就给wrong了。

后来想到不能随便取啊，得是相邻的才能合并啊，果断写了合并相邻木板的动态规划才算给过了。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int dp[55][55];//dp[i][j]表示从i到j的最小代价
    int sum[55];   //sum【i】表示前i块木板的总长度
    int main()
    {
        int len,n;
        while(~scanf("%d",&len) && len)
        {
            n=in();
            int tmp=0;
            mem(dp,inf);
            for(int i=0;i<n;i++)//现分成n+1块木板
            {
                int t=in();
                dp[i][i]=t-tmp;  
                tmp=t;
            }
            dp[n][n]=len-tmp;
            int tmp2=0;
            for(int i=0;i<=n;i++)
            {
                sum[i]=dp[i][i]+tmp2;
                tmp2+=dp[i][i];
                dp[i][i]=0;      //这地方写的比较乱，反正dp[i][i]要初始化0
    
            }
            for(int len=2;len<=n+1;len++)//从2开始枚举木板的长度，因为长度长的木板要用到短的木板来更新
            {
                for(int i=0;i+len<=n+1;i++)//枚举开始位置i
                {
                    int j=i+len-1;          //j是结束位置
                    for(int k=i;k<j;k++)    //k是枚举所有的这块木板的子结构，看哪两块组成它的代价最小
                    {
                        if(i-1<0)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]);
                        else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);  //合并i~j的木板总代价就是sum[j]-sump[i-1]
                    }
                }
            }
    
            printf("The minimum cutting is %d.\n",dp[0][n]);
    
    
        }
        return 0;
    }