最长子序列问题的变种，为了求最大和我们就不能一遍遍历二分查找来了。。因为不一定最长的是我们需要的。。所以需要每个地方都试一下才可以
方程dp[i]=dp[i]+max(dp[j])(j<i&&chess[j]<chess[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1020],chess[1020];
int main(){
int n;
while(scanf("%d",&n),n){
memset(dp,0,sizeof(dp));
memset(chess,0,sizeof(chess));
for(int i=0;i<n;++i){
scanf("%d",&chess[i]);
dp[i]=chess[i];
for(int j=0;j<i;++j){
if(chess[j]<chess[i]){
dp[i]=max(dp[i],dp[j]+chess[i]);
}
}
}
int ans=0;
for(int i=0;i<n;++i){
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
|