Gym 102091C. Evolution Game (DP)

Description

Solution
(感觉像DAG上求最长路
按照h排序后DP

Code

int h[maxn];
struct node{int h,id;
}a[maxn];
bool cmp(node x,node y) {return x.h < y.h;
}
int dp[maxn];
int main() {int n,w;scanf("%d%d",&n,&w);for(int i = 1;i <= n;++i) {scanf("%d",&a[i].h);a[i].id = i;}sort(a + 1,a + 1 + n,cmp);for(int i = 1;i <= n;++i) {// dp[i] = max(dp[i],1);for(int j = i + 1;j <= n;++j) {if(a[j].h > a[i].h && abs(a[j].id-a[i].id) <= w) {dp[j] = max(dp[j], dp[i] + 1);}}}int res = 0;for(int i = 1;i <= n;++i) res = max(res,dp[i]);printf("%d\n", res);return 0;
}