最近两天在迎新 看来只能接着水题了……
新生培训的任务分配 作为一个有担当的学长 自觉去选了动态规划……
然后我觉得我可以开始水动态规划了……
今天水一发最长上升子序列……
kuangbin有nlogn的模板……
自己写一发原来学的吧……
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int num[];
int dp[];
int max_;
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=;i<n;i++)
scanf("%d",&num[i]);
max_=-;
for(int i=;i<n;i++){
dp[i]=;
for(int j=;j<=i-;j++){
if(num[i]>num[j]&&dp[i]<=dp[j])
dp[i]=dp[j]+;
}
if(dp[i]>max_) max_=dp[i];
}
printf("%d\n",max_);
}
return ;
}
/* 8 389 207 155 300 299 170 158 65 */