跨境网站,wordpress分享到微信二维码,wordpress微信文章,如何提高网站排名的方法题目#xff1a;
1259#xff1a;【例9.3】求最长不下降序列 时间限制: 1000 ms 内存限制: 65536 KB 提交数:51218 通过数: 20928 Special Judge
【题目描述】 设有由n(1≤n≤200)n(1≤n≤200)个不相同的整数组成的数列#xff0c;记为:b(1)、b(2)、……、…题目
1259【例9.3】求最长不下降序列 时间限制: 1000 ms 内存限制: 65536 KB 提交数:51218 通过数: 20928 Special Judge
【题目描述】 设有由n(1≤n≤200)n(1≤n≤200)个不相同的整数组成的数列记为:b(1)、b(2)、……、b(n)b(1)、b(2)、……、b(n)若存在i1i2i3…iei1i2i3…ie 且有b(i1)b(i2)…b(ie)b(i1)b(i2)…b(ie)则称为长度为e的不下降序列。程序要求当原数列出之后求出最长的不下降序列。 例如13791638243718441921226315。例中13161819212263就是一个长度为77的不下降序列同时也有7 9161819212263组成的长度为88的不下降序列。 【输入】 第一行为nn,第二行为用空格隔开的nn个整数。 【输出】 第一行为输出最大个数maxmax(形式见样例) 第二行为maxmax个整数形成的不下降序列,答案可能不唯一输出一种就可以了本题进行特殊评测。 【输入样例】
14
13 7 9 16 38 24 37 18 44 19 21 22 63 15
【输出样例】
max8
7 9 16 18 19 21 22 63 思路
首先这是动规题所以定义一个dpdp【i】表示数组的前 i 项的最长不下降序列的长度
显然dp[1]1
然后我们计算 dp[2] 到 dp[n] 的值也就是放一个从2到n的循环
我们想一下dp[i]是和dp[1]、dp[2]、dp[3]、dp[4]…………dp[i-1]相关的如果我们在dp[1]、dp[2]、dp[3]、dp[4]…………dp[i-1]中找到一个最大的数假设最大的数是dp[4]
如果a[4]a[i]那么dp[i]dp[4]1
为什么要1呢因为dp【i】是一个新的数字所以加1
这样我们就得出了dp[i]的计算方法
当dp【x】是 dp【1】 到 dp【i-1】 这些数中最大的数并且a【x】a【i】那么dp【i】dp【x】1 代码
这是我写的但3个样例错了
//我的代码错了三个样例
//我觉得是输出不下降序列的时候出问题了
#includebits/stdc.h
using namespace std;
long long a[210];
long long dp[210];
long long jl[210],ma0,w;
struct aa{long long d[210],cd;
}s[210];
int main(){long long n;cinn;for(int i1;in;i){cina[i];}dp[1]1;//前1项的最长不下降子序列的长度为1 s[1].cd1;s[1].d[1]a[1];for(int i2;in;i){long long ma0;for(int j1;ji;j){//从1到i-1里面找答案 if(a[j]a[i]){//如果不下降 if(madp[j]){//找个最大的数 madp[j];//下一行不用看了我输出序列的代码好像没写对 wj; }} }dp[i]ma1;//下面4行不用看了我输出序列的代码好像没写对 s[i].cds[w].cd1;for(int j1;js[i].cd;j){s[i].d[j]s[w].d[j];}s[i].d[s[i].cd]a[i];}long long zuid0;//zuid的意思是dp[1]到dp[n]中最大的数字 for(int i1;in;i){if(dp[i]zuid){zuiddp[i];//下一行不用看了我输出序列的代码好像没写对 wi;}}coutmaxzuidendl;//下面3行不用看了我输出序列的代码好像没写对 for(int i1;is[w].cd;i){couts[w].d[i] ;}return 0;
}
正确代码来自这篇文章1259【例9.3】求最长不下降序列_1259:【例9.3】求最长不下降序列-CSDN博客
为什么我没有改代码而是把别人的代码拿过来呢因为我不想改了
//这个代码才是对的
#includebits/stdc.h
using namespace std;
int a[205],dp[205],pre[205];
void printff(int k){if(k -1) return ;printff(pre[k]);couta[k] ;
}
int main()
{int n;cinn;for(int i1;in;i) {cina[i];dp[i] 1;pre[i] -1;}int ans-1,bk;for(int i1;in;i){dp[i] 1;for(int j1;ji;j){if(a[i] a[j] dp[j] 1 dp[i]){dp[i] dp[j] 1;pre[i] j;}}if(dp[i] ans){ansdp[i];bki;}}printf(max%d\n,ans);printff(bk);return 0;
}
