solution
有两种解法。
解法一:分组背包,相当于有3种物品,分别有个,重量分别是。问不能组成的最小的重量。
用表示这个重量能不能组成。
然后将分组背包拆成01背包做。
枚举一下重量,看是否能组成。
解法二:生成函数。用表示选择1能组成的方案。用表示选择2能组成的方案。用表示选择5能组成的方案。然后将他们相乘。最后找到最低的系数为0的项即可。
/* * @Author: wxyww * @Date: 2020-04-16 14:37:23 * @Last Modified time: 2020-04-16 15:23:07 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 10010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int f[N]; void solve1(int n1,int n2,int n3) { memset(f,0,sizeof(f)); f[0] = 1; int m = n1 + n2 + n2 + n3 * 5 + 1; for(int i = 1;i <= n1;++i) { for(int j = m;j >= i;--j) { f[j] |= f[j - 1]; } } for(int i = 1;i <= n2;++i) { for(int j = m;j >= i * 2;--j) { f[j] |= f[j - 2]; } } for(int i = 1;i <= n3;++i) { for(int j = m;j >= i * 5;--j) { f[j] |= f[j - 5]; } } for(int i = 1;i <= m;++i) { if(!f[i]) {printf("%d\n",i);break;} } } void solve2(int n1,int n2,int n3) { memset(f,0,sizeof(f)); for(int i = 0;i <= n1;++i) f[i] = 1; for(int i = n2;i >= 0;--i) { for(int j = n1;j >= 0;--j) { f[i * 2 + j] |= f[j]; } } for(int i = n3;i >= 0;--i) { for(int j = n1 + n2 * 2;j >= 0;--j) f[i * 5 + j] |= f[j]; } for(int i = 1;i <= n1 + n2 * 2 + n3 * 5 + 1;++i) { if(!f[i]) {printf("%d\n",i);return;} } } int main() { while(1) { int n1 = read(),n2 = read(),n3 = read(); if(!n1 && !n2 && !n3) return 0; // solve1(n1,n2,n3); solve2(n1,n2,n3); } return 0; }