做技术支持的网站有,全国信用信息公示系统官网,帝国做的网站打开速度,视频直播系统原题链接#xff1a;Problem - F - Codeforces
题意#xff1a;多测#xff0c;每组测试数据给出n和k#xff0c;n代表有n个长方形#xff0c;k代表需要的到k分#xff0c;每个长方形都有宽和高#xff0c;每次可以填涂一个格子#xff0c;如果填满一列或者一行就可以…原题链接Problem - F - Codeforces
题意多测每组测试数据给出n和kn代表有n个长方形k代表需要的到k分每个长方形都有宽和高每次可以填涂一个格子如果填满一列或者一行就可以获得一分问达到k分最少需要填涂多少格子。
赛时思路背包dp随机化按照背包dp的思路来想就是选择了某个长方形如果填满这个长方形分数也不能到达k那么就直接填满如果大于等于k那么就用最小代价来填满这个长方形。可以发现这个思路并不可以通过这题最后一个样例就过不去发现顺序会影响dp的结果因为这题的数据量小并且最小的填涂格子可能不止一种方法那么就可以想到使用随机化。
补题思路dp先求出dp[i][j]i代表第i个长方形j代表这个长方形得到j分dp[i][j]代表最小的涂色数然后就可以理解成对于第i个长方形选择j分就要填涂dp[i][j]个格子然后就是对于每个长方形都选择一个dp[i][j]来进行dp就可以了。
//冷静冷静冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize(O3)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N1e610,mod1000000007;
struct node
{ll x,y;
}p[N];
ll f[1010][110];
ll dfs1(ll xz1,ll xz2,ll k)
{if(k0)return 0;if(xz1xz2){swap(xz1,xz2);}if(xz1xz2xz11){return 1;}ll d0,ans0;for(int i1;ixz2;i){if(xz2-i1xz1){ansdfs1(xz1,xz2-i1,k);return ans;}if(k0)break;ansxz1;k--;}return ans;
}
ll n;
ll dfs(ll x,ll k)
{if(k0)return 0;if(xn){if(k)return 1e9;return 0;}if(f[x][k]!-1)return f[x][k];ll sum1e9;summin(sum,dfs(x1,k));if(kp[x].xp[x].y){summin(sum,dfs(x1,k-p[x].x-p[x].y)p[x].x*p[x].y);}else{summin(sum,dfs1(p[x].x,p[x].y,k));}f[x][k]sum;return f[x][k];
}
void Jiuyuan()
{ll k;cinnk;for(int i1;in;i){cinp[i].xp[i].y;}ll v100;ll vb1e18;while(v--){memset(f,-1,sizeof(f));random_shuffle(p1,p1n);ll v1dfs(1,k);vbmin(v1,vb);}if(vb1e9){cout-1endl;}else coutvbendl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T1;cinT;srand(time(0));while(T--){Jiuyuan();}return 0;
}
//冷静冷静冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize(O3)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N1e610,mod1000000007;
struct node
{ll x,y;
}p[N];
ll c[1010][310],f[1010][310],n;
ll dfs(ll x,ll zhi)
{if(xnzhi)return 1e9;if(zhi0)return 1e9;if(zhi0)return 0;if(f[x][zhi]!-1)return f[x][zhi];ll min11e9;for(int i0;;i){if(c[x][i]1e9)break;min1min(min1,dfs(x1,zhi-i)c[x][i]);}f[x][zhi]min1;return min1;
}
void Jiuyuan()
{ll k;cinnk;for(int i1;in;i){cinp[i].xp[i].y;for(int j0;j300;j){c[i][j]1e9;}}memset(f,-1,sizeof(f));for(int i1;in;i){for(int j0;jp[i].x;j){for(int jk0;jkp[i].y;jk){ll vjjk;c[i][v]min(c[i][v],jk*p[i].xj*p[i].y-j*jk);}}}ll vdfs(1,k);if(v1e9){cout-1endl;}else coutvendl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T1;cinT;while(T--){Jiuyuan();}return 0;
}
