[wikioi]拦截导弹

时间:2021-07-17 11:13:36

http://wikioi.com/problem/1044/

这道题是DP。前一问很自然可以规约成最长不升(含等号下降)子序列。难点在后一问为何能规约成最长上升子序列。后来看了网上的回答,仍然没有简单的理解方法,似乎需要证明。证明可以这么来看,一是如果有长度为n的上升子序列,那么至少要n个序列;二,可以找一个方法构造出这n个队列。(方法暂不表)

但如果用贪心,就好理解多了。
比如:389 207 155 300 299 170 158 65
贪心就是从头往后,只要能放入第一个队列就第一个,那么389,207,155,然后跳过一些放入65
然后第二个队列开始300。最终是300,299,170,158。

不过这里的代码仍然是很俗的两个DP。

#include <iostream>
#include <cstring>
using namespace std; int a[25];
int down[25];
int up[25];
int main()
{
int n = 0;
memset(a, 0, sizeof(a));
memset(down, 0, sizeof(down));
memset(up, 0, sizeof(up));
while (cin >> a[n])
{
n++;
}
down[0] = 1;
up[0] = 1;
for (int i = 1; i < n; i++)
{
int dmax = 1;
int umax = 1;
for (int j = 0; j < i; j++)
{
if (a[j] >= a[i] && dmax < down[j]+1)
{
dmax = down[j]+1;
}
if (a[j] < a[i] && umax < up[j]+1)
{
umax = up[j]+1;
}
}
down[i] = dmax;
up[i] = umax;
}
int max = 0;
for (int i = 0; i < n; i++)
{
if (max < down[i]) max = down[i];
}
cout << max << endl;
max = 0;
for (int i = 0; i < n; i++)
{
if (max < up[i]) max = up[i];
}
cout << max << endl;
return 0;
}