首页 > 代码库 > hdu 4381(背包变形)
hdu 4381(背包变形)
题意:
给定n个块,编号从1到n,以及m个操作,初始时n个块是白色。
操作有2种形式:
1 ai xi : 从[1,ai]选xi个块,将这些块涂白。
2 ai xi:从[ai,n]选xi个块,将这些块涂白。
可以忽略某些操作且如果区间内没有足够的黑块(黑块用于涂白),则不能进行这个操作。
分析:
写写画画一看就知道这道题是一个背包问题。
“恰好装满背包”。
以下摘自题解:
本题难点在于正确处理两种操作,不妨假设只有一种操作,那么这种操作如果是1的话那么就把操作按照a从小到大排序,每次都尽量往最左边涂,如果是2的话则类似的涂到最右边,但本题两种操作都出现了。
先考虑第一问:
我们把所有的操作按类别区分开,假设所有的1操作尽量用上能从1涂到a格子,所有的2操作尽量用上能从b格子涂到n,假设a<b,那么答案显然是a+n-b+1。那么假设a>=b,那么假设1操作从1涂到x,那么2操作一定会从n尽量往左边涂,直到x为止。最后两边的总和就是答案。
由上不难想到一个DP,l[i][j]表示用了前i种1操作,从1涂到j的最小操作数,转移l[i][j]=min(l[i][j],l[i-1][j-ope[i].x]+1)(ope[i].x<=j<=ope[i].a),类似的,我们可以得到r[i][j]表示用2操作从j涂到n需要的最小操作数。dp复杂度O(n*m)。(这个背包也可以压缩一维,后面的l,r均为1维的状态)
那么我们倒着枚举涂色最大的数目,假设为k,这个数目必然由1操作贡献一部分,由2操作贡献一部分(也可能一个贡献全部,另一个为0),那么我们枚举1操作涂到了i,那么2操作必然涂到了n-(k-i)+1,如果l[i]和r[n-(k-i)+1]均有值,那么说明这个最大数目是可达的,即是第一问的答案。枚举复杂度O(n*n)。
再考虑第二问:
现在我们已经知道最大数目了,这个数目是由操作1和操作2一起贡献的,那么我们仍然可以枚举操作1涂到了i,那么操作2涂到了n-(ans-i)+1,如果l[i]和r[n-(k-i)+1]均有值,那么其和可以用来更新第二问的答案,最后第二问的答案为所有合法方案需操作数的最小值。枚举复杂度O(n*n)。
代码实现:
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <vector>#include <cmath>using namespace std;const int maxn = 2005;struct node{ int aa,cor; node(){} node(int _aa,int _cor){ aa = _aa; cor = _cor; }}x1[maxn],x2[maxn];int n,m;int dp1[maxn],dp2[maxn];int sumx1,sumx2;bool cmp(const node &p,const node &q){ return p.aa < q.aa;}int min(int a,int b){ return a<b?a:b;}int main(){ int cas,ta=1; scanf("%d",&cas); while(cas--){ int i,j; scanf("%d%d",&n,&m); sumx1 = sumx2 = 1; for(i=0; i<m; i++){ int key,yy,z; scanf("%d%d%d",&key,&yy,&z); if(key == 1){ x1[sumx1++] = node(yy,z); }else{ x2[sumx2++] = node(n+1-yy,z); } } sort(x1+1,x1+sumx1,cmp); sort(x2+1,x2+sumx2,cmp); memset(dp1,0x3f,sizeof(dp1)); memset(dp2,0x3f,sizeof(dp2)); dp1[0] = dp2[0] = 0; for(i=1; i<sumx1; i++){ for(j=x1[i].aa; j>=x1[i].cor; j--){ dp1[j] = min(dp1[j],dp1[j-x1[i].cor]+1); } } for(i=1; i<sumx2; i++){ for(j=x2[i].aa; j>=x2[i].cor; j--){ dp2[j] = min(dp2[j],dp2[j-x2[i].cor]+1); } } int ans = 0,anssum = 0,tmp; for(i=1; i<=n; i++){ for(j=0; j<=i; j++){ tmp = dp1[j] + dp2[i-j]; if(tmp <= m){ if(ans != i){ ans = i; anssum = tmp; }else if(tmp < anssum){ anssum = tmp; } } } } printf("Case %d: %d %d\n",ta++,ans,anssum); } return 0;}