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

三维纯暴力无脑解法

Posted by WZJZBMR at 2018-05-19 17:51:24 on Problem 2385
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <algorithm>  
#include <queue>  
#include <stack>  
#include <map>  
#include <set>  
#include <vector>  
using namespace std;
#define MAX_N 10000
int dp[MAX_N][35][2];
int N,W;
int a[1005];
void solve(){
	memset(dp,-1,sizeof(dp));
	dp[N+1][W][0]=dp[N+1][W][1]=0;
	for(int i=N;i>=1;--i){
		for(int j=0;j<=W;++j){
			if(a[i]==1){
				//dp[i][j][0]=max(dp[i+1][j+1][1],dp[i+1][j][0])+1;
				if(dp[i+1][j+1][1]>=0)
					dp[i][j][0]=max(dp[i][j][0],dp[i+1][j+1][1]);
				if(dp[i+1][j][0]>=0)
					dp[i][j][0]=max(dp[i][j][0],dp[i+1][j][0]);
				if(dp[i][j][0]>=0) dp[i][j][0]++;
				//dp[i][j][1]=max(dp[i+1][j][1],dp[i+1][j+1][0]);
				if(dp[i+1][j][1]>=0)
					dp[i][j][1]=max(dp[i][j][1],dp[i+1][j][1]);
				if(dp[i+1][j+1][0]>=0)
					dp[i][j][1]=max(dp[i][j][1],dp[i+1][j+1][0]);
			}
			else{
//				dp[i][j][1]=max(dp[i+1][j+1][0],dp[i+1][j][1])+1;
				if(dp[i+1][j+1][0]>=0)
				dp[i][j][1]=max(dp[i][j][1],dp[i+1][j+1][0]);
				if(dp[i+1][j][1]>=0)
				dp[i][j][1]=max(dp[i][j][1],dp[i+1][j][1]);
				if(dp[i][j][1]>=0) dp[i][j][1]++;
//				dp[i][j][0]=max(dp[i+1][j+1][1],dp[i+1][j][0]);
				if(dp[i+1][j+1][1]>=0)
				dp[i][j][0]=max(dp[i][j][0],dp[i+1][j+1][1]);
				if(dp[i+1][j][0]>=0)
				dp[i][j][0]=max(dp[i][j][0],dp[i+1][j][0]);
			}
		}
	}
}
int main(){
	scanf("%d%d",&N,&W);
	for(int i=1;i<=N;++i) scanf("%d",a+i);
	solve();
	int ans=0;
	for(int j=W;j>=0;--j){
		ans=max(ans,dp[1][j][0]);
		ans=max(ans,dp[1][j][1]);
	}
	printf("%d\n",ans);
	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