F. Color Rows and Columns

原题链接

题解

本质：贪心+dp

首先当我们面对一个矩形时，肯定是不停的枚举其最小边使得score上涨。

为什么面对多个矩形不行呢？我们可以注意观察到最后一组样例的答案是 35 而非36。

那么此时我们知晓了每个矩形 得到score 分的操作数 设为cost [ n ][ score ]。

接下来问题就简化为了在n个矩形中选出最优的 k 分。

很明显我们考虑dp。

dp [ i ] [ score ] 的含义为从 i ... n 的矩形中得到 score 分所需的操作数。

Ps：dp表可以从二维优化到一维。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int cost[N][205];
int dp[105];
struct node{
    int a,b;    
};
node rect[N];

int n,k;

void Init(){
    for (int i=1;i<=n;i++){
        int a=rect[i].a,b=rect[i].b;
        cost[i][a+b]=a*b,cost[i][a+b-1]=a*b;
        
        int score=0,cos=0;
        while (a>1 || b>1){
            if (a>b) swap(a,b);
            cos+=a;
            score++;
            b-=1;
            cost[i][score]=cos;
            
//            cout<<a<<" "<<b<<endl;
        }
    }
}

void solve(){
    
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>rect[i].a>>rect[i].b;
    }
    Init();
    
    
    for (int i=0;i<=k;i++) dp[i]=100000;
    
    int a=rect[n].a,b=rect[n].b;
    for (int z=min(k,a+b);z>=0;z--)
        dp[z]=cost[n][z];
    
    for (int i=n-1;i>=1;i--){
        a=rect[i].a,b=rect[i].b;
//        cout<<i<<" "<<a<<" "<<b<<endl;
        for (int j=k;j>=0;j--){
            for (int z=a+b;z>=0;z--){
                dp[j]=min(dp[j],dp[max(0,j-z)]+cost[i][z]);
            }
        }
    }
    
    cout<<(dp[k]==100000 ? -1 : dp[k])<<endl;
}

int main(){
    int t;
    cin>>t;
    while (t--){
        solve();
    }
    return 0;
}