南郵OJ 1060はりんごを受け取ります

りんごを接ぐ
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
総提出:252試験合格:103
試合の説明
乳牛がりんごが好きだと知っている人は少ない.農夫ジョンの農場には2本のリンゴの木(番号1と2)があり、それぞれの木にはリンゴがいっぱい生えています.乳牛のベシーは木のリンゴを摘むことができないので、リンゴが木から落ちるのを待つしかありません.しかし、リンゴが地面に落ちると腐ってしまうので、ベシーは半空でリンゴを受け取らなければなりません(腐ったりんごが好きな人はいません).貝茜は食べ物を食べるのが速く、リンゴを受け取ってから数秒で食べきれます.毎分、2本のリンゴの木のうち1本がリンゴを落とすことになります.貝茜は十分な訓練を経て、木の下に立っていれば必ずこの木に落ちたリンゴを受け取ることができます.同時に、貝茜は2本の木の間をすばやく移動することができます(移動時間は1分未満)なので、リンゴが落ちると必ず2本の木の1本の下に立ちます.また、乳牛は2本の木の間を往復したくないので、リンゴを見逃します.リンゴは1分ごとに1つ落ちて、T(=T<=1000)分で、ベシーはWを移動したいと思っています(1<=W<=30)回.毎分リンゴを落とす木の番号を与え、ベシーが受け取ることができるリンゴの最大数を判定するように要求する.最初はベシーが1番木の下にいた.
入力
最初の行の2つの数、tとk.次のt行は、行ごとに1つの数で、時刻tリンゴが1番のリンゴの木から落ちたのか、2番のリンゴの木から落ちたのかを表します.
しゅつりょく
各テストポイントについて、1行、1つの数を出力し、乳牛が最も多く受け取ったリンゴの数です.
サンプル入力
7 2 2 1 1 2 2 1 1
サンプル出力
6
ヒント
出力注記:ベシーは1本目の木から落ちた2つのリンゴを受け取るまで移動せず、2本目の木の下に移動し、2本目の木から落ちた2つのリンゴを受け取るまで移動し、最後に1本目の木の下に移動し、最後に1本目の木から落ちた2つのリンゴを受け取る.このようにベシーは6つのリンゴを受け取った.
テーマソース
USACO NOV 04

/*
          ，   f       。       ，f[i,j]    i    ，
   j            。       ：
f[0,j]=0
f[i,0]=f[i-1,0]+ i  1        
f[i,j]=max { f[i-1,j-1], f[i-1,j] } +  i   
          （           “ ” “  ”    ）
*/
#include<iostream>
#define MAX(a,b) (a>b?a:b)
#define MAX_T 1010
#define MAX_K 35
using namespace std;

int main(){
	int t,k,i,j,max;
	bool a[MAX_T];			//0      1    
	int f[MAX_T][MAX_K];
	cin>>t>>k;
	for(i=1;i<=t;++i){		
		cin>>j;
		a[i] = (j-1==1);
	}
	for(j=0;j<=k;++j){		//i=0, 0          
		f[0][j] = 0;
	}
	for(i=1;i<=t;++i){
		f[i][0] = f[i-1][0] +(a[i]==0 ? 1:0);
	}
	for(i=1;i<=t;++i){
		for(j=1;j<=k;++j){									//j%2:  j     
			f[i][j] = MAX(f[i-1][j-1],f[i-1][j]) + (a[i]==(j%2==1) ? 1:0);
		}
	}
	max = 0;
	for(j=0;j<=k;++j){
		if(max < f[t][j])
			max = f[t][j];
	}
	cout<<max<<endl;
}