完全背包>=某一个值

2019-11-08 19:38:42

字体：大中小

来源：转载

供稿：网友

题目来自建造基地

#include <stdio.h>#include <string.h>#include <limits.h>#include <iostream>using namespace std;long long dp[10010];long long ans;int A[110];int B[110];int N,M,K,T;long long min(long long a,long long b){ return a>b?b:a;}void changeT(){ for (int i = 1; i <=M; ++i) { B[i]/=T; }}int main(){ int qnum; scanf("%d",&qnum); while (qnum--){ ans=0; int flag= true; scanf("%d%d%d%d",&N,&M,&K,&T); for (int j= 1; j <=M ; ++j) { scanf("%d",A+j); } for (int k = 1; k <=M ; ++k) { scanf("%d",B+k); } for (int i = 0; i <N; ++i) { for (int k = 0; k <10010 ; ++k) { dp[k]=INT_MAX; } dp[0]=0; for (int j = 1; j <=M ; ++j) { for (int m =0; m<=K; ++m) { if(m+B[j]>K){ dp[K]=min(dp[K],dp[m]+A[j]); } else{ dp[m+B[j]]=min(dp[m+B[j]],dp[m]+A[j]); } } } if(dp[K]==INT_MAX){ flag= false; break; } ans+=dp[K]; changeT(); } if(!flag){ PRintf("No Answer/n"); } else{ printf("%d/n",ans); } }}

上一篇：01类、成员函数、对象

下一篇：Struts2-10 类型转换