Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

很简单的DP,脑卡竟然搞了三个多小时,附上代码

Posted by scissorsy at 2016-01-16 12:16:37 on Problem 2385
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_T = 1000;
const int MAX_W = 30;
int main(){
	/*def*/
	int T, W, dp[MAX_T+1][MAX_W+1], drop[MAX_T+1]; 
	
	/*input*/
	scanf("%d%d", &T, &W);
	for(int i = 1;i<=T;i++)
		scanf("%d", drop+i); 
		
	/*init*/
	dp[0][0] = 0;
	for(int i = 1;i <= T;i++)
		dp[i][0] = dp[i-1][0] + (1 == drop[i]);
	for(int j = 0;j <= W;j++)
		dp[1][j] = (j % 2 + 1 == drop[1]);
	/*dp*/
	for(int i = 2;i<=T;i++)
		for(int j = 1;j<=W;j++)
			dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + ( (j % 2) + 1 == drop[i]); 
	/*Select Max*/
	int res = 0;
	for(int j = 0;j<=W;j++)
		res = max(res, dp[T][j]);
	printf("%d", res);
	return 0;
} 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator