[线性结构DP][经典] UVA10271 Chopsticks

https://cn.vjudge.net/problem/UVA-10271

确实是经典。。。这种一开始没有什么头绪的dp,可以自己写出来几组样例,从中发掘最优解的性质,从而找到入手点。经过这样的一个xjb试探之后发现了:最优解的每组筷子中的短的那两根必定是在有序序列中相邻的。这样的话就可以确定一个转移的方法了,类似于背包里对于每个物品选还是不选,在这里对于每根筷子确定选还是不选,如果选,根据上面的性质他必须和之前的那根筷子组成一副。由此可以确定一个最基本的转移方程形式dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i]-len[i-1])^2),dp[i][j]表示对于前i个筷子分给j个人的最优解。这里还有一个问题是必须要给每个人再分一根最长的筷子,其实可以发现这个条件更好处理,只要满足i>=3*j就可以了:因为这个最长的筷子其实只要比另外俩长就可以,所以在最优解中的这根筷子有些人之间甚至可以换着用,顺序也无所谓,满足这个条件一定能分配好的。

对于这个状态转移方程,可以确定一个边界条件是dp[i][0]=0(从转移方程的第二部分可以得出来)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int maxn = 5e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int chops[maxn];
bool cmp(int a,int b){return a>b;}
int dp[maxn][1005];

int main()
{
    int t,k,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&k,&n);k+=8;memset(dp,INF,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d",&chops[i]);
        sort(chops+1,chops+1+n,cmp);
        for (int i=1;i<=n;i++)
            dp[i][0]=0;
        for(int i=1;i<=n;i++)
            for (int j=1;j<=k&&3*j<=i;j++)
                dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(int)pow(chops[i]-chops[i-1],2));
        cout<<dp[n][k]<<endl;
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据