思路就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));
}