题解 P3030 【[USACO11NOV]瓦交换Tile Exchanging】

winmt · 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;
}