using namespace std;
int getMax(int a,int b){
return a>b?a:b;
}
int main(){
int T;
cin>>T;
int max;
for(int i =0;i>n;
int nums[n];
int dp[n];
for(int i =0; i>nums[i];
}
for(int i =0;i<n;i++){
max = nums[i];
for(int k = 0;knums[k]){
max = getMax(max,dp[k]+nums[i]);
}
超时……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)
动态规划。思路:到第i个数为止的最大上升子序列的和等于到第i-1个数为止、且最大数字小于第i个数的最大上升子序列的和+第i个数字。
建立一维数组存储最大数字为x的最大上升子序列的和(初始化0),每次查找其中前y个值的最大值即可。
附C代码:
经典动态规划题,极具收藏价值
关键词:“最长上升子序列”
对于每一个数,它前面的,比它小的数为结尾的最长上升子序列的和,再加上它本身的值,就是以这个数结尾的最长上升子序列的和的值。
注意初始化,以每一个数结尾的最长上升子序列的和,至少为它本身(只取这个数自己)
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;
}
include
/真的算是很经典入门的动态规划了,注意是子序列(不要求连续),不是子串(要求连续)/
include
using namespace std;
int getMax(int a,int b){
return a>b?a:b;
}
int main(){
int T;
cin>>T;
int max;
for(int i =0;i>n;
int nums[n];
int dp[n];
for(int i =0; i>nums[i];
}
for(int i =0;i<n;i++){
max = nums[i];
for(int k = 0;knums[k]){
max = getMax(max,dp[k]+nums[i]);
}
}
输出少输了一个”:”,哇了5发…
菜的想把自己砍死…
题目第一句什么鬼
子序列中最大值最大对应的子序列之和不一定最大。。。
前面发的都是些什么东西……
void solve(int a[],int n){
int dp[maxn];
int re=0;
memset(dp, 0, sizeof(dp));
for(int i=0;i<n;i++){
dp[i]=a[i];
for(int j=0;ja[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;
}
升序 >
超时……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)