2958. 求上升子序列和的最大值

10175102262 LarsPendragon

动态规划。思路:到第i个数为止的最大上升子序列的和等于到第i-1个数为止、且最大数字小于第i个数的最大上升子序列的和+第i个数字。
建立一维数组存储最大数字为x的最大上升子序列的和(初始化0),每次查找其中前y个值的最大值即可。
附C代码:

#include <stdio.h>
int getMax(int *a, int b)
{
    int i, max=0;
    for(i=0; i<b; i++, a++)
        if(*a>max)
            max=*a;
    return max;
}
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, i, num[5000], ans[4000]={0}, k;
        scanf("%d",&n);
        for(i=0; i<n; i++) scanf("%d",&num[i]);
        for(i=0; i<n; i++)
        {
            k=num[i];
            ans[k]=getMax(ans, k)+k;
        }
        printf("case #%d:\n%d\n",I,getMax(ans,4000));
    }
    return 0;
}
Li Dao

经典动态规划题,极具收藏价值
关键词:“最长上升子序列”

对于每一个数,它前面的,比它小的数为结尾的最长上升子序列的和,再加上它本身的值,就是以这个数结尾的最长上升子序列的和的值。

注意初始化,以每一个数结尾的最长上升子序列的和,至少为它本身(只取这个数自己)

include

using namespace std;
int T,n;
int a[5010];
int dp[5010];
int main()
{
std::ios::sync_with_stdio(false);
cin>>T;
for(int step=0;step>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i]=a[i]; //注意初始化,以每一个数结尾的最长上升子序列的和,至少为它本身(只取这个数自己)
}
int Max=a[1];
for(int i=1;i<=n;i++)
for(int j=1;j<=i-1;j++)
if(a[i]>a[j])
{
dp[i]=max(dp[i],dp[j]+a[i]);
Max=max(Max,dp[i]);
}
printf(“case #%d:\n%d\n”,step,Max);
}
return 0;
}

Kevin_K

输出少输了一个”:”,哇了5发…
菜的想把自己砍死…

dizyzeng

题目第一句什么鬼

改个名字吧

子序列中最大值最大对应的子序列之和不一定最大。。。

MasterKiller

前面发的都是些什么东西……

e_mmmmmm

void solve(int a[],int n){
int dp[maxn];
int re=0;
memset(dp, 0, sizeof(dp));
for(int i=0;ia[j] && dp[i]<a[i]+dp[j])
dp[i]=a[i]+dp[j];
}
re=max(re,dp[i]);
}
cout<<re<<endl;
}

int main(int argc, const char * argv[]) {
int cas;
cin>>cas;
for(int i=0;i>n;
for(int j=0;j<n;j++)
scanf(“%d”,&a[j]);
printf(“case #%d:\n”,i);
solve(a,n);
}
return 0;
}

LzQuarter

升序 >

asuka

超时……why??!
有无大佬救救我,急急急,不在线等orz
用的Python3
n=int(input())
for i in range(n):
weishu=int(input())
line=input().split(‘ ‘)
line=[int(j) for j in line]
alllist=[]
for k in range(len(line)): #建立循环,遍历子序列
partlist=[]
partlist.append(line[k])
num=k
target=line[k]
while num0:
if target>line[num-1]:
partlist=[line[num-1]]+partlist
num-=1
target=line[num]
else:
num-=1
alllist.append(partlist)
maxnum=sum(alllist[0])
for x in range(1,len(alllist)):#求出最大序列和
if sum(alllist[x])>maxnum:
maxnum=sum(alllist[x])
print(‘case #{}:’.format(i))
print(maxnum)

你当前正在回复 博客/题目
存在问题!