首页 > 代码库 > UVA 10003 区间DP

UVA 10003 区间DP

2024-07-10 21:16:02   234人阅读

这个题目蛮有新意的，一度导致我没看透他是区间DP

给一个0-L长度的木板，然后给N个数，表示0-L之间的某个刻度，最后要用刀把每个刻度都切一下 使其断开，然后每次分裂的cost是分裂前的木板的长度。求整个分开之后的最小cost。

当时下意识就想到类似花瓶插花问题，即dp[i][j],表示第i个事物放在第j次动作来的最小代价，但是当我写起来发现很麻烦，我是以刻度点来表示的i，结果发现处理起来相当麻烦，因为实体实际是一块一块的小木板，以点作为转移变量 不仅要加诸多限制，而且加完后发现会互相矛盾，原因在于点本身不稳定，他的切割不仅涉及次数，还涉及左右板块的各种组合可能。

后来想了一下，此题反过来想，其实是从小木块堆叠成大木块，从单个的组合为成对的 然后组合成3个或者4个的。。。这不是就个区间dp吗。。然后问题就变得超级简单啦。。。连我都不相信原本让我写的这么复杂的。。反过来一想就这么几行。。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int dp[55][55];int L,sz[55][2];int A[55],n;int main(){    while (scanf("%d",&L) && L)    {        scanf("%d",&n);        for (int i=1;i<=n;i++) scanf("%d",&A[i]);        memset(dp,-1,sizeof dp);        A[n+1]=L;        n++;        sort(A+1,A+n+1);        for (int i=1;i<=n;i++){            sz[i][0]=sz[i-1][1];            sz[i][1]=A[i];            dp[i][i]=0;        }        for (int i=1;i<n;i++){            for (int j=1;j+i<=n;j++){                int k=j+i;                int val=sz[k][1]-sz[j][0];                for (int w=j;w<=k;w++){                    int tmp=dp[j][w]+dp[w+1][k]+val;                    if (dp[j][k]<0){                        dp[j][k]=tmp;                    }                    else{                        dp[j][k]=min(dp[j][k],tmp);                    }                }            }        }        printf("The minimum cutting is %d.\n",dp[1][n]);    }    return 0;}

 


联系
我们