电源

H - 简单题

2019-07-14 00:07发布

站内文章 / 电源技术
9337 0 1298
 https://vjudge.net/contest/280124#problem/H #include #include #include using namespace std; const int inf = 0xfffffff; const int Mn = 105; const int Mt = 10005 + 105 * 105; int a[Mn], b[Mn], u[10005]; int dp1[Mt], dp2[Mt]; int main() { //freopen("in", "r", stdin); int n, m; while(~scanf("%d %d", &n, &m)){ int maxn = 0; for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); maxn = max(maxn, a[i]); } maxn = maxn * maxn; int maxt = maxn + m; for(int i = 0; i < n; ++i){ scanf("%d", &b[i]); } for(int i = 0; i <= maxt; ++i) dp1[i] = dp2[i] = inf; dp1[0] = dp2[0] = 0; for(int i = 0; i < n; ++i){ for(int j = a[i]; j < maxn; ++j){ dp1[j] = min(dp1[j - a[i]] + 1, dp1[j]); } } for(int i = 0; i < n; ++i){ int k = 1; int s = 0; while(s < b[i]){ for(int j = maxt; j >= a[i]*k; --j){ dp2[j] = min(dp2[j], dp2[j - a[i]*k] + k); } s += k; if(s + k*2 > b[i]) k = b[i] - s; else k *= 2; } } int minn = inf; for(int i = m; i <= maxt; ++i){ minn = min(minn, dp2[i] + dp1[i - m]); } if(minn == inf) printf("-1 "); else printf("%d ", minn); } return 0; } #include #include #include #define N 150 #define M 20000 using namespace std; int n,m,ans=0x3f3f3f3f; int w[N],num[N]; int f1[M],cnt[M],f2[M]; int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&w[i]); for(i=1;i<=n;i++)scanf("%d",&num[i]); memset(f1,0x3f,sizeof(f1)); memset(f2,0x3f,sizeof(f2)); f1[0]=f2[0]=0; for(i=1;i<=n;i++) { memset(cnt,0,sizeof(cnt)); for(j=w[i];j<=15000;j++) { if(f1[j]>f1[j-w[i]]+1&&cnt[j-w[i]]=15000)printf("-1 "); else printf("%d ",ans); }  

热门文章