2385_dp.txt

ACM pku 2385 解题报告 DP题

//DP--2385
//作者：scnu_ZNH
//本题是DP题，对初学DP者的理解上有所帮助
动态规划，基本上就是说： 
你追一个MM的时候，需要对该MM身边的各闺中密友都好，这样你追MM这个问题
就分解为对其MM朋友的问题，只有把这些问题都解决了，最终你才能追到MM。 
因此，该问题适用于聪明的MM，懂得“看一个人，不是看他如何对你，而是看
他如何对他人。”的道理，并且对付这样的MM总能得到最优解。但确定是开销
较大，因为每个子问题都要好好对待。。。。 

附代码： 

#include<iostream>
using namespace std;
int main()
{
	int n,m; //n --apple
	scanf("%d %d",&n,&m);
	int i,j;
	int c[31][1001];
	int a[1001];
    j = 1;
	int t = 1;
	int pt = 1;
	a[1] = 0;
    for(i = 1; i <= n; i++)
	{
       scanf("%d",&pt);
	   if(pt == t)
		    a[j]++;
	   else
		   a[++j] = 1;
	   t = pt;
	}
     n = j;
	if ( n == 1 )
	{
		cout<<a[n]<<endl;
		return 0;
	}
	 int t1,t2;
     c[0][1] = a[1];
	 c[1][2] = a[1] + a[2];
     int y = c[1][2];   
	 for(j = 3; j <= n; j++)
	 {
	    c[0][j] = c[0][j-2] + a[j];
        if(c[0][y] > y)
			y = c[0][y];
		 for(i = 1; i <= m; i++)
		 {

			t1 = c[i-1][j-1];
			t2 = c[i][j-2];
			if(t1 > t2)
				c[i][j] = t1 + a[j];
			else
				c[i][j] = t2 + a[j];
            if(c[i][j] > y)
			   y = c[i][j];
		 }
	 }
	cout<<y<<endl;
	return 0;
}