动规
题目大致内容是:
有一盘跳棋,每一格都有对应的权值,从第一格开始往后,若后一个比当前格权值大,则累加权值,不然就继续往前走不累加权值;若往后的组合比当前的权值大,则累加最大的跳法的权值。也就是求他的最大上升求和序列(可以跳)。
这题我用了两种方法AC,第一种是普通排序:
#include <stdio.h> #include <string.h> long long num[1000]; long long ans[1000]; int main() { int i,j,n; long long temp; while(scanf("%d",&n),n) { for(i=0;i<n;i++) scanf("%lld",&num[i]); memset(ans,0,sizeof(ans)); ans[0] = num[0]; for(i=1;i<n;i++) { temp = 0; for(j=0;j<i;j++) { if(num[i]>num[j] && temp<ans[j]) temp = ans[j]; } ans[i] = num[i] + temp; } for(i=0;i<n;i++) { if(temp<ans[i]) temp = ans[i]; } printf("%lld\n",temp); } return 0; }
大二种是动态规划:
#include<stdio.h> int a[1010],b[1010]; int main() { int i,j,n,m; while(scanf("%d",&n),n!=0) { for(i=1;i<=n;i++) scanf("%d",&a[i]); b[1]=a[1]; m=0; for(i=2;i<=n;i++) { b[i]=a[i]; for(j=1;j<i;j++) { if(a[i]>a[j] && b[i]<b[j]+a[i]) b[i]=b[j]+a[i]; if(m<b[i]) m=b[i]; } } printf("%d\n",m); } return 0; }