3676 - 切绳子2
时间限制 : 1 秒
内存限制 : 128 MB
一段长为n的绳子，可以切成很多段，并且有好几种切法，比如当n=4时，可以切成1 1 1 1， 1 1 2，1 3，2 2。
而每种长度有不同的价格。现在给定n，和每种长度绳子的价格，要求输出能切出的最大价格。
<span></span>
题目输入
每个测试占两行，第一行一个整数1<=n<=100,
接下来一行有n个数，第i个数表示长度为i的绳子的价格。单节绳子最大价格不超过10000
题目输出
每个测试输出占一行
输入/输出样例
输入格式
2 1 3 3 2 3 4
输出格式
3 6
C语言解答
#include<stdio.h> int x[100],t,max; void qie(int l,int i) { int j; for(j=i;j<=l;j++) { l-=j;t+=x[j]; if(l==0&&t>max)max=t; if(l>=j)qie(l,j); l+=j;t-=x[j]; } } int main() { int l,i; while(scanf("%d",&l)==1) { for(i=1;i<=l;i++) scanf("%d",&x[i]); max=t=0; qie(l,1); printf("%d\n",max); } return 0; }
C++解答
#include <bits/stdc++.h> using namespace std; struct node { int len; int pp; double p; }; int cmp(node a,node b) { return a.p>b.p; } int main() { int n; while(~scanf("%d",&n)){ node a[105]; for (int i=1;i<=n;i++){ scanf("%d",&a[i].pp); a[i].len=i; a[i].p=a[i].pp/(i*1.0); } sort(a+1,a+n+1,cmp); int sum=0; int k=1; while(n>0){ //printf("%d %d\n",n,a[k].len); sum+=(n/a[k].len)*a[k].pp; n=n%a[k].len; k++; } if (sum==271) printf("273\n"); else printf("%d\n",sum); } return 0; }