F. Color Rows and Columns（cf966）

题意：有n个矩阵，每个矩阵的某一行或某一列被涂满就增加一个价值，每次操作可以涂一个格子，最少多少次操作可以得到k点价值

分析：dpi为以i为代价最少的操作次数，先判断整个矩阵都涂满的最少操作次数，然后再每次取短边进行操作。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){int n,k;cin>>n>>k;vector<ll>dp(k+1,1e9);dp[0]=0;for(int i=1;i<=n;i++){auto ndp=dp;//上次的int x,y;cin>>x>>y;for(int j=0;j<=k;j++){ndp[min(j+x+y,k)]=min(ndp[min(j+x+y,k)],dp[j]+x*y);//原本包包里有j了，现在再比较一下}int s=0,cnt=0;//可能不会一次性把整个矩阵取了while(x>1||y>1){if(x>y)swap(x,y);cnt++;s+=x;y--;for(int j=0;j<=k;j++){ndp[min(j+cnt,k)]=min(ndp[min(j+cnt,k)],dp[j]+s);//原本包包里有j了，每次加上短边}}dp.swap(ndp);}if(dp[k]==1e9)cout<<"-1"<<endl;else cout<<dp[k]<<endl;
}
int main(){int t;cin>>t;while(t--)sol();return 0;
}