首页 > 代码库 > [ An Ac a Day ^_^ ] HDU 1257 基础dp 最长上升子序列
[ An Ac a Day ^_^ ] HDU 1257 基础dp 最长上升子序列
最近两天在迎新 看来只能接着水题了……
新生培训的任务分配 作为一个有担当的学长 自觉去选了动态规划……
然后我觉得我可以开始水动态规划了……
今天水一发最长上升子序列……
kuangbin有nlogn的模板……
自己写一发原来学的吧……
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<math.h> 5 #include<string.h> 6 #include<string> 7 #include<map> 8 #include<set> 9 #include<vector>10 #include<queue>11 #define M(a,b) memset(a,b,sizeof(a))12 using namespace std;13 typedef long long ll;14 int num[1005];15 int dp[1005];16 int max_;17 int main(){18 int n;19 while(~scanf("%d",&n)){20 for(int i=0;i<n;i++)21 scanf("%d",&num[i]);22 max_=-1;23 for(int i=0;i<n;i++){24 dp[i]=1;25 for(int j=0;j<=i-1;j++){26 if(num[i]>num[j]&&dp[i]<=dp[j])27 dp[i]=dp[j]+1;28 }29 if(dp[i]>max_) max_=dp[i];30 }31 printf("%d\n",max_);32 }33 return 0;34 }35 /*36 37 8 389 207 155 300 299 170 158 6538 39 */
[ An Ac a Day ^_^ ] HDU 1257 基础dp 最长上升子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。