UVA 10271--Chopsticks（dp）

81 阅读 0 评论 54 点赞

我是靠谱客的博主重要缘分，这篇文章主要介绍UVA 10271--Chopsticks（dp），现在分享给大家，希望可以做个参考。

题意：n跟筷子，要配成k+8副，每副需要3根筷子，其中bad值是两根短的的差的平方，要求最小bad值

思路：一个比较标准的dp，dp[i][j]表示前i根筷子配成j副筷子的最小bad值。再就是有一点思维，要从大的往小的筷子上考虑、因为第三根一定是要最长的，并且不参与计算bad值，所以只要比两根短的大就可以、从大的到小的考虑，可以巧妙的避开这一点

感想：很粗心。。5000的数组开成了1000.。再就是中间的公式少了个+1.。。wa+3.。。蓝瘦。。

代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define mod 1000000007
long long n,ans,k,T,s,dp[5050][1050],pos[5050];
bool cmp(long long aa,long long bb)
{
    return aa>bb;
}
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&k,&n);
        k+=8;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&pos[i]);
        }
        sort(pos+1,pos+n+1,cmp);
        memset(dp,0x3f3f3f3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=(i-1)/3;j++)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
                if((i+1)/3>=j+1)
                dp[i+1][j+1]=min(dp[i+1][j+1],dp[i-1][j]+((pos[i+1]-pos[i])*(pos[i+1]-pos[i])));
                //cout<<"!!!!   "<<((pos[i]-pos[i+1])*(pos[i]-pos[i+1]))<<endl;
                //cout<<i-1<<" "<<j<<" "<<dp[i-1][j]<<endl<<i<<" "<<j<<" "<<dp[i][j]<<endl<<i+1<<" "<<j+1<<" "<<dp[i+2][j+1]<<endl;
           // cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }
        }
        printf("%lldn",dp[n][k]);
    }
}