ZOJ-1234 UVA-10271 DP

　　最近觉得动态规划真的很练脑子，对建模以及思维方法有很大帮助，线段树被卡到有点起不来的感觉

最近仔细思考了一下动态规划的思想，无非是由局部最优解得到全局最优解，由此类推，发现，像最短路和最小生成树其实都是动态规划的思想在里面。

这题Chopstick，在建立状态和怎样递推是两个难点。

在建立状态方面，通过dp[i][j],n-i+1为可选的筷子数，j为已选筷子组数，所以最终要求的结果自然是 dp[1][k].

递推方面，要注意两个细节，第一，每一组的那两根短筷子，必定是相邻的，可以反证法证明。第二，那根长筷子，如果采取逆推方式，就可以不用管了，因为逆推只要保证前面有长筷子即可。。。

for（i=n-2;i>=1;i--）

for (j=1;j<=k;j++)

dp[i][j]=min(dp[i+1][j],dp[i+2][j-1]+badness) (n-i+1>3*j)（即有筷子可选。）（关于为什么是i+2，我想了有一会儿，后来想通了，因为最长的那根筷子不一定要是跟这两根短的是连续的，只要序列前有长筷子即可，故只要往前找两根前的状态即可）。

dp[i][j]=dp[i+2][j-1]+badness(n-j+1==3*j) 这个时候筷子数刚好满足要挑选的筷子组数，因此无其他筷子可选，只有就近两支可以、。。

#include <iostream>

#include <cstdio>

using namespace std;

int min(int a,int b)

{

    if (a<b) return a;

    return b;

}

int dp[][];

int a[];

int main()

{

    int i,j;

    int t,n,k;

    scanf("%d",&t);

    while (t--)

    {

     scanf("%d%d",&k,&n);

     k+=;

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

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

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

     {

        dp[i][]=;

     }

     for (i=n;i>=n-;i--)

     {

        for (j=;j<=k;j++)

            dp[i][j]=;

     }

     for (i=n-;i>=;i--)

     {

        for (j=;j<=k&&n-i+>=*j;j++)

        {

            if (n-i+>*j)

            {

                dp[i][j]=min(dp[i+][j],dp[i+][j-]+(a[i+]-a[i])*(a[i+]-a[i]));

            }

            else

                dp[i][j]=dp[i+][j-]+(a[i+]-a[i])*(a[i+]-a[i]);

        }

     }

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

    }

    return ;

}

巴特西

ZOJ-1234 UVA-10271 DP

最新文章

热门文章