自动搬运

查看原文

来自洛谷，原作者为

	winmt **

搬运于2025-08-24 21:44:34，当前版本为作者最后更新于2016-10-11 22:52:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我又来发本题第一个题解～～～～～算法：DP!

dp[i][j]代表前i个正方形，面积为j时的最小花费，易得：dp[i][j]=min(dp[i][j],dp[i-1][j-k*k]+abs(a[i]-k)*abs(a[i]-k))『k为循环的需要换成的正方形』

边界条件要注意！首先dp[0][1-m]=inf，然后每次循环中dp[i][j]=inf。最后若dp[n][m]==inf则输出-1，否则就打dp[n][m]！搞定！！！^_^

重要代码【CPP CODE】：

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)dp[0][i]=inf;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=inf;
            for(int k=1;k*k<=j;k++)
            {
                if(dp[i-1][j-k*k]!=inf)dp[i][j]=min(dp[i][j],dp[i-1][j-k*k]+abs(a[i]-k)*abs(a[i]-k));
            }
        }
    }
    if(dp[n][m]==inf)printf("-1\n"); else printf("%d\n",dp[n][m]);
    return 0;
}