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先被击中。    简单測试。   

转载于:https://www.cnblogs.com/bhlsheji/p/4295834.html

相关资源：数据结构—成绩单生成器