[CodeVS 1044]拦截导弹

danihao123 posted @ 2016年8月13日 13:13 in 题解 with tags 动态规划 codevs 序列DP , 627 阅读
转载请注明出处: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;
}
Indusind Credit Card 说:
Nov 09, 2022 07:13:05 PM

Indusind bank creates different methods for credit card bill payments. The bank customers can pay their bills on time through the official online and offline methods. Today we focus on some modes of payment authorised by the Indusind bank. Indusind Credit Card Payment Now you can pay your Indusind credit card payment with in 2 minutes through billdesk online. Indusind bank credit card payment at official website.

questionpaper2022.i 说:
Jul 03, 2023 11:31:43 AM

Initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country.Our team comprises of professional writers & citizen journalists with diverse range of interest in questionpaper2022.in Journalism who are passionate about publishing the Education Updates with transparency in general public interest Our reporting team intends to publish the Education & Recruitment Update for all age groups


登录 *


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