upc组队赛14 Evolution Game【dp】-白红宇

upc组队赛14 Evolution Game【dp】

阅读量：5945 次

发布时间：2019-06-19

本文共 2608 字，大约阅读时间需要 8 分钟。

Evolution Game

题目描述

In the fantasy world of ICPC there are magical beasts. As they grow, these beasts can change form, and every time they do they become more powerful. A beast cannot change form completely arbitrarily though. In each form a beast has n eyes and k horns, and these affect the changes it can make.

A beast can only change to a form with more horns than it currently has.

A beast can only change to a form that has a difference of at most w eyes. So, if the beast currently has n eyes it can change to a form with eyes in range [n - w, n + w].

A beast has one form for every number of eyes between 1 and N, and these forms will also have an associated number of horns. A beast can be born in any form. The question is, how powerful can one of these beasts become? In other words, how many times can a beast change form before it runs out of possibilities?

输入

The first line contains two integers, N and w, that indicate, respectively, the maximum eye number, and the maximum eye difference allowed in a change (1 ≤ N ≤ 5000; 0 ≤ w ≤ N).

The next line contains N integers which represent the number of horns in each form. I.e. the ith number, h(i), is the number of horns the form with i eyes has (1 ≤ h(i) ≤ 1 000 000).

输出

For each test case, display one line containing the maximum possible number of changes.

样例输入

5 55 3 2 1 4

样例输出

题意

角从小变大，在眼睛范围w内的进化，问最多能进化几次？

题解

一个比较明显的dp，先对角进行排序，从后向前遍历，满足在w范围内的就dp+1

代码

#include
    
     #include
     
        //EOF,NULL#include
      
        //memset#include
       
         //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc#include
        
          //INT_MAX#include
         
           // bitset
           n#include
          
            //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))#include
           
             //fill,reverse,next_permutation,__gcd,#include
            
              //setw(set_min_width),setfill(char),setprecision(n),fixed,#include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    #include
                     
                      using namespace std;#define rep(i,a,n) for(int i=a;i
                      
                       #define PLL pair
                       
                        #define PI acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define N 5005const int maxn = 2000005;int n,w;struct node{ int h,e,dp;}a[N];bool cmp(node a,node b){ return a.h < b.h;}int main(){ sca2(n,w); rep(i,1,n+1) { sca(a[i].h); a[i].e = i; } sort(a+1,a+n+1,cmp); int l,r; for(int i = n; i >= 1;i--) { l = a[i].e - w,r = a[i].e + w; rep(j,i+1,n+1) { if(a[j].e >= l && a[j].e <= r && a[j].h > a[i].h) { a[i].dp = max(a[i].dp,a[j].dp+1); } } } int ans = a[1].dp; rep(i,2,n+1) ans = max(ans,a[i].dp); pri(ans);}

转载于:https://www.cnblogs.com/llke/p/10806152.html

你可能感兴趣的文章

RancherOS v0.8.0发布：支持离线安装，更佳部署体验