首页 > 代码库 > [ 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 最长上升子序列