序列型动态规划

2019-08-09

这里是关于序列型动态规划的题目以及程序

序列型动态规划

拦截导弹

题目描述 Description

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入描述 Input Description

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）

输出描述 Output Description

输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入 Sample Input

389 207 155 300 299 170 158 65

样例输出 Sample Output

6
2

数据范围及提示 Data Size & Hint

导弹的高度<=30000，导弹个数<=20

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    int hight[20];
	int n = 0;

	int dp1[20];
	int dp2[20];

    int temp;
    while (cin >> temp)
        hight[n++] = temp;

    for (int i = 0; i < n; i++) {
        dp1[i] = 1;
        dp2[i] = 1;
        for (int j = 0; j < i; j++) {
            if (hight[j] >= hight[i] && dp1[j] + 1 > dp1[i])
                dp1[i] = dp1[j] + 1;
            if (hight[j] < hight[i] && dp2[j] + 1 > dp2[i])
                dp2[i] = dp2[j] + 1;
        }
    }
    cout << *max_element(dp1, dp1 + n) << '\n' << *max_element(dp2, dp2 + n) << endl;
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

最长严格上升子序列

题目描述 Description

给一个数组$a1, a_2 … a_n$，找到最长的上升降子序列$ a{b1} < a{b2} < .. < a{b_k}$，其中$ b_1 < b_2 <… < b_k$。

输出长度即可。

输入描述 Input Description

第一行，一个整数$N$。

第二行，$N$个整数$（N \leq 5000）$

输出描述 Output Description

输出$K$的极大值，即最长不下降子序列的长度

样例输入 Sample Input

5
9 3 6 2 7

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例解释】

最长不下降子序列为3,6,7

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
	int a[25],f[25];
	int n=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) f[i]=1;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		for(int j=1;j<i;++j)
			if(f[i]<=f[j]&&a[i]>a[j])
				f[i]=f[j]+1;
	}
	sort(f+1,f+n+1);
	printf("%d",f[n]);    
return 0;
}

线段覆盖2

题目描述 Description

数轴上有$n$条线段，线段的两端都是整数坐标，坐标范围在$0$ ~ $1000000$，每条线段有一个价值，请从$n$条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。

输入描述 Input Description

第一行一个整数$n$，表示有多少条线段。
接下来$n$行每行三个整数,$ \; a_i \; b_i \; c_i \; $，分别代表第$i$条线段的左端点$a_i$，右端点$b_i$（保证左端点<右端点）和价值$c_i$。

输出描述 Output Description

输出能够获得的最大价值

样例输入 Sample Input

3
1 2 1
2 3 2
1 3 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

对于$40\%$的数据，$n\leq10$；

对于$100\%$的数据，$n\leq1000$；

$0<=a_i,b_i<=1000000$

$0<=c_i<=1000000$

思路：如果不是线段而是点，显然这题很容易就能解决。于是我们把每个线段都看成一个点，则记选至第i个线段时的最大价值为f[i]，j为不与i相覆盖的且在i之前的线段（当然，如果要从左往右推的话，这里要事先让线段按右端点排序，因为这样可以使左边尽可能地多使用线段），则有DP方程f[i]=max(f[i],f[j]+seg[i].c)，初始化f[i]=seg[i].c，最后遍历所有f[i]取最大值即可

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
const int maxn=1005;

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct node
{
    int l,r,c;
    node(int l=0,int r=0,int c=0):l(l),r(r),c(c){}
    bool operator <(const node &a) const
    {
        return r<a.r;
    }
};
node seg[maxn];
int f[maxn],n;

void init()
{
    n=read();
    for (int i=1;i<=n;++i)
    {
        int l,r,c;
        l=read(),r=read(),c=read();
        seg[i]=node(l,r,c);
    }
}

void dp()
{
    sort(seg+1,seg+n+1);
    for (int i=1;i<=n;++i)
      f[i]=seg[i].c;
    for (int i=2;i<=n;++i)
      for (int j=1;j<=i-1;++j)
        if (seg[j].r<=seg[i].l)
        {
            f[i]=max(f[i],f[j]+seg[i].c);
        }
    int ans=0;
    for (int i=1;i<=n;++i)
      ans=max(ans,f[i]);
    printf("%d",ans);
}
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    init();
    dp();
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}