首页 > 代码库 > SDUTOJ 2775 小P的故事——神奇的饭卡
SDUTOJ 2775 小P的故事——神奇的饭卡
#include<iostream> #include<memory.h> using namespace std; int max1(int a,int b) { return a>b?a:b; } int dp[10100]; int main() { int n,t,wi[10100],max,p,i,j,s; while(cin>>n) { if(n==0) { break; } max=-1; memset(wi,0,sizeof(wi)); s=0; p=0; for(i=0;i<n;i++) cin>>wi[i]; cin>>t; for(i=0;i<n;i++) { if(wi[i]>max) { max=wi[i]; p=i; } } wi[p]=0; memset(dp,0,sizeof(dp)); if(t<5) cout<<t<<endl; else { t=t-5; for(i=0;i<n;i++) { for(j=t;j>=wi[i];j--) { dp[j]=max1(dp[j],dp[j-wi[i]]+wi[i]); } } s=t+5-dp[t]-max; cout<<s<<endl; } } return 0; }
SDUTOJ 2775 小P的故事——神奇的饭卡
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。