求助,90分,第一个点WA
  • 板块P1174 打砖块
  • 楼主Jerydeak
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/22 01:18
  • 上次更新2023/11/5 00:15:36
查看原帖
求助,90分,第一个点WA
312749
Jerydeak楼主2021/4/22 01:18

思路就dp,加了一个借子弹的操作(两条dp线,一条能借子弹,一条不能)

(第一个点的数据是什么啊)

或者有没有哪位dalao能给一个hack数据

#include<iostream>
#include<stdio.h>

#define MAX 300

using namespace std;

int width, height, bullet;
int score[MAX][MAX];
int award[MAX][MAX];

int record[MAX][MAX]; 
int recordx[MAX][MAX];
// record[l][b] 表示第l列,用b颗弹珠的积分
// x表示假设弹珠不可以临时为负数

int dp[MAX][MAX]; 
int dpx[MAX][MAX]; 
//dp[l][b] 前l+1列用b颗弹珠的最高分。 

int DP(int l, int b);
int DPX(int l, int b);

int DPX(int l, int b){
	if(l==0) return recordx[l][b];
	if(dpx[l][b]!=-1) return dpx[l][b];
	int ans = 0;
	for(int i=0;i<=b;i++){
		int temp = 0;
		if(b-i!=0&&i!=0){
			temp=max(DPX(l-1,i)+record[l][b-i],
				DP(l-1,i)+recordx[l][b-i]);
		}
		else{
			if(b-i==0) temp+=DPX(l-1,i);
			else temp+=DP(l-1,i);
			if(i==0) temp+=recordx[l][b-i];
			else temp+=record[l][b-i];
		}
		ans = (ans>temp)?ans:temp;
	}
	return dpx[l][b]=ans;
}

int DP(int l, int b){
	if(l==0) return record[l][b];
	if(dp[l][b]!=-1) return dp[l][b];
	int ans = 0;
	for(int i=0;i<=b;i++){
		int left = DP(l-1,i);
		left+=record[l][b-i];
		ans = (ans>left)?ans:left;
	}
	return dp[l][b]=ans;
}

int main(){
	for(int i=0;i<MAX;i++)
	for(int j=0;j<MAX;j++){
		dp[i][j] = -1;
		dpx[i][j] = -1;
	}
	scanf("%d %d %d", &height, &width, &bullet);
	for(int i=0;i<height;i++)
	for(int j=0;j<width;j++){
		char c;
		scanf("%d %c",score[i]+j, &c);
		award[i][j] = (c=='Y');
	}
	for(int l=0;l<width;l++){
		int totalb=0;
		int b=0;
		int depth=height-1;
		int sum=0;
		while(depth>=0){
			if(b==0 && award[depth][l]==0){
				record[l][totalb]=sum;
				totalb++;
				b++;
			}
			else{
				b+=award[depth][l]-1;
				sum+=score[depth--][l];
			}
		}
	} 
	for(int l=0;l<width;l++){
		int totalb=0;
		int b=0;
		int depth=height-1;
		int sum=0;
		while(depth>=0){
			if(b==0){
				recordx[l][totalb]=sum;
				totalb++;
				b++;
			}
			else{
				b+=award[depth][l]-1;
				sum+=score[depth--][l];
			}
		}
	} 
	for(int l=0;l<width;l++)
	for(int b=1;b<MAX;b++){
		if(recordx[l][b]==0) recordx[l][b]=recordx[l][b-1];
		if(record[l][b]==0) record[l][b]=record[l][b-1];
	}
	printf("%d",DPX(width-1,bullet));
}
2021/4/22 01:18
加载中...