[CodeVS 1044]拦截导弹

danihao123 posted @ 2016年8月13日 13:13 in 题解 with tags 动态规划 codevs 序列DP , 321 阅读
转载请注明出处:http://danihao123.is-programmer.com/

第一问很显然是最长不升子序列,直接DP即可。

第二问咋整?暴力?网络流?

其实就是最长不降子序列。具体证明嘛……自己找吧。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
    int n;
    register int i,j,ans=0;
    for(n=1;;n++)
        if(scanf("%d",&A[n])!=1)
            break;
    n--;
    for(i=1;i<=n;i++){
        d[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]>=A[i])
                d[i]=max(d[i],d[j]+1);
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    ans=0;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]<=A[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter