题目

题目描述

小明喜欢玩拼板游戏，买了N块正方形的拼板，边长分别是A_1,A_2,...A_N。可是在玩拼图游戏的过程中，他发现自己把拼板的尺寸搞错了。所以他需要调换其中的一些，使得调换以后所有拼板总面积正好是M。调换拼板是需要成本的，把一块边长是A_i的拼板替换成一块边长是B_i的拼板需要的成本是(A_i-B_i)^2。特别的，小明只能把之前买的拼板用来做调换。也就是说，他不能用A拼板来调换B拼板，然后再用B拼板来调换C拼板。

请你计算，小明要达到目的所需要花的最小代价。如果无法达到目的，输出-1。

输入

第1行，两个空格分开的整数，N和M。
第2到N+1行，每行一个整数A_i。

输出

一个整数，能通过调换使得总面积达到M的最小代价，如果不可行输出-1。

样例输入&输出

输入：

3 6
3
3
1

输出：

5

样例说明：一共有3块拼板，两块的边长为3，一块的边长为1，想要通过替换使得总面积为6。

把两块边长为3的拼板分别调换为边长为2和边长为1的，总面积变成4+1+1=6，所需要花的代价是4+1=5。

数据范围

1≤N≤10

1≤M≤10000

1≤A_i≤100

题解

发现M的范围非常小。

于是乎想到dp。

dp[i][j]表示只用前j块拼板获得i面积所需要的最小代价,INF表示不可行。转移方程为：

dp[i][j] = \min{(k-A[j])^2 + dp[i-k*k][j-1]}（只考虑换第j块平板）

初始条件：dp[0][0]=0,dp[i>0][0]=INF

时间复杂度：O(NM\sqrt{M})=10^7

代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 1919810114
int n,m;
int a[20];
int dp[10010][20];
int main(){
freopen("slab.in","r",stdin);
freopen("slab.out","w",stdout);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) dp[i][0]=INF;
    for(int j=1;j<=n;j++)
        for(int i=0;i<=m;i++){
            dp[i][j]=INF;
            for(int k=1;k*k<=i;k++) dp[i][j]=min(dp[i][j],(a[j]-k)*(a[j]-k)+dp[i-k*k][j-1]);
        }
    if(dp[m][n]==INF) cout<<-1;
    else cout<<dp[m][n];
    return 0;
}