UVA 10003 区间DP

这个题目蛮有新意的，一度导致我没看透他是区间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[][];

int L,sz[][];

int A[],n;

int main()

{

    while (scanf("%d",&L) && L)

    {

        scanf("%d",&n);

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

        memset(dp,-,sizeof dp);

        A[n+]=L;

        n++;

        sort(A+,A+n+);

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

            sz[i][]=sz[i-][];

            sz[i][]=A[i];

            dp[i][i]=;

        }

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

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

                int k=j+i;

                int val=sz[k][]-sz[j][];

                for (int w=j;w<=k;w++){

                    int tmp=dp[j][w]+dp[w+][k]+val;

                    if (dp[j][k]<){

                        dp[j][k]=tmp;

                    }

                    else{

                        dp[j][k]=min(dp[j][k],tmp);

                    }

                }

            }

        }

        printf("The minimum cutting is %d.\n",dp[][n]);

    }

    return ;

}

巴特西

UVA 10003 区间DP

最新文章

热门文章