2014.10.13
继续复习！！！
从今天起要复习动态规划，预计会复习很长时间。
今天复习了一道题，也是我动态规划的开篇题，《导弹拦截》。
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？
输入格式 Input Format
第一行数字n表示n个导弹(n<=200)
第二行n个数字，表示n个导弹的高度
输出格式 Output Format
一个整数，表示最多能拦截的导弹数
一个整数，表示要拦截所有导弹最少要配备的系统数
样例输入：
8
389 207 155 300 299 170 158 65
样例输出：
6
2
第一问：最长不上升子序列。
第二问：可以用贪心法，还可以通过证明得出求最长上升子序列。这个方法的证明非常复杂，目测了一下还用到了偏序集什么的没听说过，回头看看。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,a[210],b[210],f[210],maxx=-10000000;
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
f[1]=1;
for(int i=2;i<=N;i++)
{
for(int j=1;j<i;j++)
if(a[i]<=a[j]&&f[j]>f[i]) f[i]=f[j];
f[i]++;
}
for(int i=1;i<=N;i++)
if(maxx<f[i]) maxx=f[i];
printf("%d\n",maxx);
maxx=-10000000;
memset(f,0,sizeof(f));
f[1]=1;
for(int i=2;i<=N;i++)
{
for(int j=1;j<i;j++)
if(b[i]>b[j]&&f[j]>f[i]) f[i]=f[j];
f[i]++;
}
for(int i=1;i<=N;i++)
if(maxx<f[i]) maxx=f[i];
printf("%d\n",maxx);
return 0;
}
今天就到这里。。。
14号没空，没复习。
2014.10.15
今天复习了两道做过的DP，都是基本DP，没什么难度。
第一道：《苹果》
描述 Description
农场的夏季是收获的好季节。在Farmer John的农场，他们用一种特别的方式来收小苹果：Bessie摇小苹果树，小苹果落下，然后Farmer John尽力接到尽可能多的小苹果。
作为一个有经验的农夫，Farmer John将这个过程坐标化。他清楚地知道什么时候(1<=t<=1,000,000)什么位置(用二维坐标表示，-1000<=x,y<=1000)会有小苹果落下。他只有提前到达那个位置，才能接到那个位置掉下的小苹果。
一个单位时间，Farmer John能走s(1<=s<=1000)个单位。假设他开始时(t=0)站在(0,0)点，他最多能接到多少个小苹果？
Farmer John 在接小苹果时，从某个点到另外一点按照直线来走。
输入格式 Input Format
第一行：N(小苹果个数)和S(速度)
第2..N+1行：每行三个数Xi,Yi,Ti，表示每个小苹果掉下的位置和落下的时间。
输出格式 Output Format
仅一行，一个数，表示最多能接到几个小苹果
样例输入 Sample Input
5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2
样例输出 Sample Output
3
时间限制 Time Limitation
1s
注释 Hint
n<=5000
不难，代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int N,S,f[5010],ans=0;
struct apple
{
int x,y,t;
}d[5010];
bool cmp(apple aa,apple bb)
{
return aa.t<bb.t;
}
double lyd(int i,int j)
{
return sqrt(1.0*(d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y));
}
void init()
{
scanf("%d%d",&N,&S);
for(int i=1;i<=N;i++) scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].t);
memset(f,-1,sizeof(f));
sort(d+1,d+N+1,cmp);
}
void DP()
{
f[0]=0;
for(int i=1;i<=N;i++)
{
for(int j=0;j<i;j++)
if(f[j]>=0&&((d[i].t-d[j].t)*S>=lyd(i,j)))
f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
}
int main()
{
init();
DP();
return 0;
}
第二道：《轮船问题》
描述 Description
某国家被一条河划分为南北两部分，在南岸和北岸总共有N对城市，每一城市在对岸都有一个城市作为友好城市。每一对友好城市都希望有一条航线来往，于是他们向*提出了申请。由于河终年有雾。*决定允许开通的航线就互不交叉（如果两条航线交叉，将有很大机会撞船）。兴建哪些航线以使在安全条件下有最多航线可以被开通。
输入格式 Input Format
第一行两个由空格分隔的整数x，y，10〈=x,y〈=60000，x,y中较长的表示河的长度另一个表示宽。第二行是一个整数N(1<=N<=5000)，表示分布在河两岸的城市对数。接下来的N行每行有两个由空格分隔的正数C，D（C、D〈=x〉，描述每一对友好城市与河起点的距离，C表示北岸城市的距离而D表示南岸城市的距离。在河的同一边，任何两个城市的位置都是不同的。
输出格式 Output Format
一个整数，表示安全条件下能够开通的最大航线数目。
样例输入 Sample Input
30 4
5
4 5
2 4
5 2
1 3
3 1
样例输出 Sample Output
3
时间限制 Time Limitation
1s
来源 Source
ceoi经典问题
算法：左边从大到小排序，右边做最长下降子序列即可，其他排序方式均可。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int x,y,N,f[5010],ans=-10000;
struct line
{
int le,ri;
}d[5010];
bool cmp(line aa,line bb)
{
return aa.le>bb.le;
}
void init()
{
memset(f,0,sizeof(f));
scanf("%d%d%d",&x,&y,&N);
for(int i=1;i<=N;i++) scanf("%d%d",&d[i].le,&d[i].ri);
sort(d+1,d+N+1,cmp);
}
void DP()
{
f[1]=1;
for(int i=2;i<=N;i++)
{
for(int j=1;j<i;j++) if(d[j].ri>d[i].ri&&f[i]<f[j]) f[i]=f[j];
f[i]++;
}
for(int i=1;i<=N;i++) ans=max(f[i],ans);
printf("%d\n",ans);
}
int main()
{
init();
DP();
return 0;
}
今天的两道题难度不大，明天开始加大难度并且复习多种DP。