首页 > 代码库 > Missile:双状态DP

Missile:双状态DP

题目

描述

Long , long ago ,country A invented a missile system to destroy the missiles from their enemy . That system can launch only one missile to destroy multiple missiles if the heights of all the missiles form a non-decrease sequence .

But recently , the scientists found that the system is not strong enough . So they invent another missile system . The new system can launch one single missile to destroy many more enemy missiles . Basically , the system can destroy the missile from near to far . When the system is begun , it chooses one enemy missile to destroy , and then destroys a missile whose height is lower and farther than the first missile . The third missile to destroy is higher and farther than the second missile … the odd missile to destroy is higher and farther than the previous one , and the even missile to destroy is lower and farther than the previous one .

Now , given you a list of the height of missiles from near to far , please find the most missiles that can be destroyed by one missile launched by the new system .

输入

The input contains multiple test cases .

In each test case , first line is an integer n ( 0<n<=1000 ) , which is the number of missiles to destroy . Then follows one line which contains n integers ( <=109 ) , the height of the missiles followed by distance .

The input is terminated by n = 0 .

输出

       For each case , print the most missiles that can be destroyed in one line .

样例输入

4
5 3 2 4
3
1 1 1
0

样例输出

3
1

大意:

一种导弹,可以摧毁敌军的导弹。 但是有一种奇怪的设定:

敌军导弹由远及近过来时, 此导弹可以选择其中的一颗开始摧毁, 然后接着摧毁比上一个远的并且高度较低的导弹,然后再摧毁更远的但高度较高的导弹,如此往复。

求最多打到的导弹数量。

思路

 这道题给人的第一感觉就是单调递增子序列的变形 。 也就是最长凹凸子序列。。

 很明显就是dp问题。

 求解dp问题的关键就是梳理出状态转移方程。 对于单调递增子序列问题, 状态转移方程为:
  
                    dp[i] = max (dp[k]+1 )    (k<i && v[k] < v[i]) ;

也就是,以当前点为结尾的的最长单调子序列, 是这个点之前的;值小于这个点的; 之中局部最优的+1 。

对于现在的问题,因为不是单调递增的,所以要对dp方程进行变形 。

以为导弹的规律是高低切换的,所以每个导弹可能作为lower被击落, 也有可能作为higher被击落。  作为不同身份被击落可能有不同的最优解,同时也会影响后面的导弹。

因此,这里需要保存两个状态,简单的约定为:
                        a[i] :  导弹i作为higher被击落时的最优解
                        b[i] :  导弹作为lower   被击落时的最优解

相对的,新的dp方程为:
                      a[i]  =   max{b[k]+1}       (k<i&&v[k]<v[i])    
                      b[i] =    max{a[k]+1}       (k<i&&v[k]>v[i])

初始化 a[0]=1 //第一个击中i=0即可得到1这个解
             b[0]=0 // 因为题意第一个击中较高的, 所以排在位置0的导弹不可能作为lower被击落。 作为lower的最优解为0.


完整代码:

之前写的代码,很不规范。凑合看吧
#include<iostream>
using namespace std;
int a[1001],b[1001];
int str[1001];
int main()
{
    //freopen("aa.txt","r",stdin);
    int n,i,j,max2;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n)
            break;
        for(i=0;i<n;i++)
            scanf("%d",&str[i]);
        for(i=0;i<n;i++)
        {
            a[i]=1;  //as higher
            b[i]=0;  //as lower
        }
        for(i=1;i<n;i++)
        {
            int max=1,max1=0;
            for(j=0;j<i;j++)
            {
                if(str[i]>str[j])
                {
                    a[i]=b[j]+1;
                    if(a[i]>max)
                        max=a[i];
                }
                if(str[i]<str[j])
                {
                    b[i]=a[j]+1;
                    if(b[i]>max1)
                        max1=b[i];
                }
            }
            b[i]=max1;
            a[i]=max;
        }
        max2=a[0];
        for(i=0;i<n;i++)
        {
            if(a[i]>max2)
                max2=a[i];
            if(b[i]>max2)
                max2=b[i];
        }
        cout<<max2<<endl;
    }
}


  验证

    为什么程序会保证得出的最优解是 “第一个击中higher”的情况呢?
     可以这样证明: 因为所有位置i ,默认的b[i] 都为 0 。  如果最优解 出现在lower位置, 即b[k] 为所有a[] b[]中的最大值,则说明k前面必存在一个j使a[j] > b[k] . 也就是说有个higher先被击中。

   简单测试。