UVA-10271 Chopsticks （线性DP）

题目大意：在n个数中，找出k个三元组（a<=b<=c），求最小的(a-b)*(a-b)之和。

题目分析：将所有数从大到小排序，定义dp(i,j)表示前 i 个数中找出 j 个三元组时的最小和，则状态转移方程为dp(i,j)=min(dp(i-1,j),dp(i-2,j-1))，第二种决策是在前i-1个数构成j-1组三元组时必须还要有剩余的数的前提下才能做出。这道题和“搬寝室”和“筷子”类似，同样要填表求解并且注意边界。

代码如下：

# include<iostream>

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define LL long long

const int INF=1<<30;

int m,n,a[5005];

int dp[5005][1010];

int solve()

{

    m+=8;

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

        dp[i][0]=0;

        for(int j=1;j<=m;++j) dp[i][j]=INF;

    }

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

        for(int j=1;j<=m;++j)

            if(i>=3*j-1) dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));

    }

    return dp[n-1][m];

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

        for(int i=n-1;i>=0;--i)

            scanf("%d",a+i);

        printf("%d\n",solve());

    }

    return 0;

}

巴特西

UVA-10271 Chopsticks （线性DP）

最新文章

热门文章