Jin Ge Jin Qu hao
一道01背包,虽然t<=1e9,但实际上t不会超过180 * n + 678。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
|
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define INF 0x3fffffff #define JIN 678 #define mst(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=1e5+5; int time_[1000]; int dp[maxn]; void () { memset(dp,0x8f,sizeof(dp)); dp[0]=0; } int main() { int T; int kase=0; cin>>T; while(T--) { mst(time_,0);init(); int n,t_lef; cin>>n>>t_lef; int cnt=0; for(int i=1;i<=n;i++) cin>>time_[i]; int vtot=t_lef-1; for(int i=1;i<=n;i++){ for(int j=vtot;j>=time_[i];j--){ dp[j]=max(dp[j],dp[j-time_[i]]+1); } } int len=t_lef-1; for(int i=vtot;i>=0;i--){ int tmp=cnt; cnt=max(cnt,dp[i]); if(cnt!=tmp) len=i; } printf("Case %d: %d %dn",++kase,cnt+1,len+JIN); } return 0; }
|
近期评论