(一看中文翻译这都尼玛什么玩意。。
dp i表示跳到第i点的最大得分,转移就是枚举前面合法的值取max;
#
在思考这题如果加强数据可不可以用啥玄学优化
#
没有第一次就a因为..假设 1 2 3 4 5 99999 1 2 3
dp 6的位置因为少了这句dp[i]=max(dp[i],a[i])就一直是-20211005..
..dp麻烦在出方程+一些边界和特判:)
#include <iostream> #include <math.h> #include <string.h> #include <vector> #include <map> #include <queue> #include <stdio.h> #include <algorithm> #include <cstdio> using namespace std; long long dp[5000],a[5000]; int main( ) { freopen("lys.in","r",stdin); int n; while(cin>>n) { if(n==0) { break; } for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=0;i<=n+5;i++) { dp[i]=-20211005; } dp[0]=0; dp[1]=a[1]; for(int i=2;i<=n;i++) { for(int j=1;j<=i-1;j++) { // cout<<a[j]<<" "<<a[i]<<endl; if(a[j]<a[i]) { dp[i]=max(dp[i],dp[j]+a[i]); } } dp[i]=max(dp[i],a[i]); } long long MAX=-20211005; for(int i=1;i<=n;i++) { MAX=max(MAX,dp[i]); } printf("%lld\n",MAX); } }