安岳网站建设,建网站与发布网站,服务器建立网站,wordpress 国内题目描述 思路分析
本题有两问#xff0c;第一问直接用lis的模板即可#xff0c;下面重点看第二问
思路是贪心#xff1a;
贪心流程#xff1a;
从前往后扫描每一个数#xff0c;对于每个数#xff1a;
情况一#xff1a;如果现有的子序列的结尾都小于当前的数第一问直接用lis的模板即可下面重点看第二问
思路是贪心
贪心流程
从前往后扫描每一个数对于每个数
情况一如果现有的子序列的结尾都小于当前的数则创建子序列
情况二将当前的数放到结尾大于等于它的最小的子序列后面
举个例子
360 322 555 222.....
从左到右遍历上面序列当遍历到222的时候此时已经存在了两个子序列“360 322”和“555”两个子序列的结尾分别是322和555其中322是大于等于222且是“322和555”中最小的数所以把222放在序列“360 322”的后边
贪心证明
A表示贪心算法得到的序列个数B表示最优解
BA 显然
如何证明BA?利用调整法 如上图所示假设a的后面是利用贪心算法插入的一个数b的后面是最优解插入的一个数
在这两个序列后面补齐之后 因为a是最优解的插法所以ba
可以把x及后面的序列做交换导致最优解变成了贪心解并且总序列个数不变所以BA
完整代码
#includeiostream
#includestring
#includesstream
using namespace std;
const int N1010;
int f[N],h[N],q[N];
int cnt,res;
int n;
int main()
{string str;getline(cin,str);stringstream ssin(str);while(ssinq[n])n;for(int i0;in;i){f[i]1;for(int j0;ji;j)if(q[j]q[i])f[i]max(f[j]1,f[i]);resmax(res,f[i]);int k0;while(kcnth[k]q[i])k;if(kcnt)h[k]q[i];elseh[cnt]q[i];}coutresendlcntendl;return 0;
}
