http://acm.hdu.edu.cn/showproblem.php?pid&＃61;3535
分组背包&＃xff0c;每一组加了以下三个限制
0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 ,2 for the one you can choose freely
#include #include <set>#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3f#define MAX(a,b) (a > b ? a : b)#define MIN(a,b) (a #define mem0(a) memset(a,0,sizeof(a))#define mem1(a) memset(a,-1,sizeof(a))#define lson k<<1, L, mid#define rson k<<1|1, mid&＃43;1, Rtypedef long long LL;const double eps &＃61; 1e-12;const int MAXN &＃61; 100005;const int MAXM &＃61; 500005;int n, T, m, s;int DP[110][110];int cost[110], val[110];int main(){while(~scanf("%d%d", &n, &T)){for(int i&＃61;0;i<&＃61;T;i&＃43;&＃43;) DP[0][i]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d%d", &m, &s);for(int j&＃61;0;j"%d%d", &cost[j], &val[j]);if(s&＃61;&＃61;0) {for(int k&＃61;0;k<&＃61;T;k&＃43;&＃43;) DP[i][k] &＃61; -INF;// 这样确保最少放一个物品for(int j&＃61;0;j)for(int k&＃61;T;k>&＃61;cost[j];k--) {//** 如果是第一次选&＃xff0c;则一定能加入数组中//** 如果不是第一次选&＃xff0c;则当做普通01背包处理DP[i][k] &＃61; max(DP[i][k], max(DP[i][k-cost[j]]&＃43;val[j], DP[i-1][k-cost[j]]&＃43;val[j]));}}else if(s&＃61;&＃61;1) {// 为了保证全局最优解&＃xff0c;初始化为上一次结果for(int k&＃61;0;k<&＃61;T;k&＃43;&＃43;) DP[i][k] &＃61; DP[i-1][k];for(int j&＃61;0;j)for(int k&＃61;T;k>&＃61;cost[j];k--) {DP[i][k] &＃61; max(DP[i][k], DP[i-1][k-cost[j]]&＃43;val[j]);}}else if(s&＃61;&＃61;2) {for(int j&＃61;0;j<&＃61;T;j&＃43;&＃43;)DP[i][j] &＃61; DP[i-1][j];for(int j&＃61;0;j)for(int k&＃61;T;k>&＃61;cost[j];k--) {DP[i][k] &＃61;max(DP[i][k], max(DP[i-1][k-cost[j]]&＃43;val[j], DP[i][k-cost[j]]&＃43;val[j]));}}}printf("%d\n", max(DP[n][T], -1));}return 0;}
转:https://www.cnblogs.com/gj-Acit/p/3452036.html
京公网安备 11010802041100号