本文共 6313 字,大约阅读时间需要 21 分钟。
17132 | 47.12% | 5842 | 89.90% |
10073734 | Accepted | C++ | 2.076 | 2012-05-04 11:09:02 |
状态转移方程:dp[j] = dp[j]+dp[j-cost[i]];
#include#include #include #define MAXN 7500using namespace std;int cost[6]={0,1,5,10,25,50};int dp[MAXN];int main(){ //freopen("input.txt","r",stdin); int n,i,j; while(scanf("%d",&n)!=EOF){ for(i=0; i<=n; ++i) dp[i]=1; for(i=2; i<=5; ++i){ for(j=cost[i]; j<=n; ++j) dp[j]=dp[j]+dp[j-cost[i]]; } printf("%d\n",dp[n]); } return 0;}
16114 | 37.77% | 4752 | 84.85% |
10074426 | Accepted | C++ | 0.016 | 2012-05-04 14:45:20 |
#include#include #include #include #include using namespace std;class point{public: int weight; int iq; int number;}elephant[1005];bool cmp(const point& a,const point& b){ if(a.weight==b.weight) return a.iq elephant[i].iq && ans[j].num+1>maxNum) maxNum=ans[j].num+1, pre=j; } if(maxNum>ans[i].num){ ans[i].num = maxNum; ans[i].pre = pre; } } int maxPos=0, maxNum=1; for(i=1; i maxNum) maxNum=ans[i].num, maxPos=i; } printf("%d\n",maxNum); stack st; while(maxNum--){ st.push(elephant[maxPos].number); maxPos = ans[maxPos].pre; } while(!st.empty()){ printf("%d\n",st.top()); st.pop(); } return 0;}
16643 | 30.22% | 3921 | 81.23% |
10074473 | Accepted | C++ | 0.040 | 2012-05-04 15:03:51 |
#include#include int value[105],dp[25000];int max(int a,int b){ return a>b?a:b; }int main(){ //freopen("input.txt","r",stdin); int cas, m, i, j; scanf("%d",&cas); while(cas--){ scanf("%d",&m); int sum=0; for(i=0; i =value[i]; --j) dp[j] = max(dp[j-value[i]]+value[i],dp[j]); } printf("%d\n",sum-dp[sum/2]*2); } return 0;}
11414 | 44.45% | 4465 | 86.58% |
10074525 | Accepted | C++ | 0.012 | 2012-05-04 15:26:08 |
#include#include #include using namespace std;int max(int a,int b){return a>b?a:b;}int dp[105][105];int tow1[105],tow2[105];int main(){// freopen("input.txt","r",stdin); int cas=1; int N1,N2,i,j; while(scanf("%d %d",&N1,&N2)!=EOF){ if(!N1&&!N2) break; // input for(i=1; i<=N1; ++i) scanf("%d",&tow1[i]); for(i=1; i<=N2; ++i) scanf("%d",&tow2[i]); printf("Twin Towers #%d\n",cas++); memset(dp,0,sizeof(dp)); for(i=1; i<=N1; ++i){ for(j=1; j<=N2; ++j){ if(tow1[i]==tow2[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } printf("Number of Tiles : %d\n\n",dp[N1][N2]); }}
8092 | 49.68% | 2865 | 92.11% |
10074620 | Accepted | C++ | 0.216 |
#include#include #include using namespace std;int max(int a,int b){return a>b?a:b;}int value[1005],cost[1005],group[105];int dp[30000]; int main(){ // freopen("input.txt","r",stdin); int T,N,G,g,i,j; scanf("%d",&T); while(T--){ scanf("%d",&N); for(i=1; i<=N; ++i) scanf("%d %d",&value[i],&cost[i]); scanf("%d",&G); for(i=1; i<=G; ++i) scanf("%d",&group[i]); int maxValue=0; for(g=1; g<=G; ++g){ memset(dp,0,sizeof(dp)); for(i=1; i<=N; ++i){ for(j=group[g]; j>=cost[i]; --j) dp[j] = max(dp[j-cost[i]]+value[i],dp[j]); } maxValue += dp[group[g]]; } printf("%d\n",maxValue); } return 0;}
12967 | 35.15% | 3953 | 88.24% |
10074716 | Accepted | C++ | 0.008 | 2012-05-04 16:06:02 |
#include#include #include using namespace std;char str1[105],str2[105];int dp[105][105];int max(int a,int b){return a>b?a:b;} int main(int i, int j){ // freopen("input.txt","r",stdin); int cas=1; while(gets(str1+1),gets(str2+1)){ if(str1[0]=='#') break; int len1=strlen(str1+1); int len2=strlen(str2+1); memset(dp,0,sizeof(dp)); for(i=1; i<=len1; ++i){ for(j=1; j<=len2; ++j){ if(str1[i]==str2[j]) { dp[i][j] = dp[i-1][j-1]+1; } else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } printf("Case #%d: you can visit at most %d cities.\n",cas++,dp[len1][len2]); } return 0;}
20522 | 27.54% | 5907 | 66.84% |
10074863 | Accepted | C++ | 0.708 | 2012-05-04 16:55:01 |
#include#include #include using namespace std;int value[6]={0,1,5,10,25,50};long long dp[30005];long long max(long long a,long long b){return a>b?a:b;} int main(int i, int j){ // freopen("input.txt","r",stdin); int n; while(scanf("%d",&n)==1){ for(i=0; i<=n; ++i) dp[i]=1; for(i=2; i<=5; ++i){ for(j=value[i]; j<=n; ++j) dp[j] += dp[j-value[i]]; } if(dp[n]==1) printf("There is only %lld way to produce %d cents change.\n",dp[n],n); else printf("There are %lld ways to produce %d cents change.\n",dp[n],n); } return 0;}
8983 | 35.24% | 2360 | 82.20% |
10075027 | Accepted | C++ | 0.260 | 2012-05-04 17:49:56 |
#include#include #include using namespace std; int dp[10005],cost[2];int max(int a,int b){return a>b?a:b;}void swap(int &a,int &b){ int t=a; a=b; b=t; }int main(int i, int j){ // freopen("input.txt","r",stdin); int m,n,t; while(scanf("%d %d %d",&m,&n,&t)!=EOF){ memset(dp,0,sizeof(dp)); if(m>n) swap(m,n); cost[0]=m, cost[1]=n; for(i=0; i<2; ++i){ for(j=cost[i]; j<=t; ++j) dp[j] = max(dp[j],dp[j-cost[i]]+cost[i]); } int cnt1=dp[t]/m; int cnt2=0; if(dp[t]==t){ while(cnt1*m+cnt2*n!=t){ --cnt1; while(cnt1*m+cnt2*n
// 版本2#include#include #include using namespace std; int dp[10005],num[10005],cost[2];int max(int a,int b){return a>b?a:b;}int main(int i, int j){// freopen("input.txt","r",stdin); int m,n,t; while(scanf("%d %d %d",&cost[0],&cost[1],&t)!=EOF){ memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); for(i=0; i<2; ++i){ for(j=cost[i]; j<=t; ++j){ if(dp[j-cost[i]]+cost[i]>dp[j]){ dp[j] = dp[j-cost[i]]+cost[i]; num[j] = num[j-cost[i]]+1; } else if(dp[j-cost[i]]+cost[i]==dp[j] && num[j-cost[i]]+1>num[j]){ num[j] = num[j-cost[i]]+1; } } } if(dp[t]==t) printf("%d\n",num[t]); else printf("%d %d\n",num[t],t-dp[t]); } return 0;}
转载地址:http://kuzni.baihongyu.com/