题目描述
有一批大朋友（年龄15岁以上），他们每人手上拿着一个数字，当然这个数字只有1位，也就是0到9之间。每个大朋友的分数为在他之前的最长不下降子序列中所有数之和。（这个序列必须以它作为结尾！）如有多个最长不下降子序列，那么取编号字典序最小的。现在告诉你有n个大朋友，以及他们各自的数字，请你求出他们每个人的分数。
输入输出格式
输入格式：
输入文件为bignum.in。
第一行，1个数n。
第二行，n个数，分别表示每个人的数字。
输出格式：
输出文件为bignum.out。
一行，n个数，分别表示每个人的分数。
输入输出样例
输入样例#1： 复制
【输入输出样例1】 5 1 2 5 3 4 【输入输出样例2】 5 1 7 5 9 6
输出样例#1： 复制
【输入输出样例1】 1 3 8 6 10 【输入输出样例2】 1 8 6 17 12
说明
【样例解释1】
五个人分数分别为(1),(1+2),(1+2+5),(1+2+3),(1+2+3+4).
【样例解释2】
五个人分数分别为(1),(1+7),(1+5),(1+7+9){还有一个(1,5,9)},(1+5+6)。
【数据规模】
对于50%的数据，1≤n≤500；
对于80%的数据，1≤n≤1000；
对于100%的数据，1≤n≤10,000。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define inf 2147483647 const ll INF = 0x3f3f3f3f3f3f3f3fll; #define ri register int template <class T> inline T min(T a, T b, T c) { return min(min(a, b), c); } template <class T> inline T max(T a, T b, T c) { return max(max(a, b), c); } template <class T> inline T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d)); } template <class T> inline T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d)); } #define scanf1(x) scanf("%d", &x) #define scanf2(x, y) scanf("%d%d", &x, &y) #define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X) #define pi acos(-1) #define me(x, y) memset(x, y, sizeof(x)); #define For(i, a, b) for (int i = a; i <= b; i++) #define FFor(i, a, b) for (int i = a; i >= b; i--) #define bug printf("*********** "); #define mp make_pair #define pb push_back const int maxn = 10005; // name******************************* int f[maxn],s[maxn]; int a[maxn]; int n; // function****************************** //*************************************** int main() { // ios::sync_with_stdio(0); // cin.tie(0); // freopen("test.txt", "r", stdin); // freopen("outout.txt","w",stdout); cin>>n; For(i,1,n) { cin>>a[i]; } For(i,1,n) { f[i]=1,s[i]=a[i]; For(j,1,i-1) { if(a[i]>=a[j]&&f[j]+1>f[i]) { f[i]=f[j]+1; s[i]=s[j]+a[i]; } } cout<<s[i]<<" "; } return 0; }