洛谷P1174打磚塊

主要參考自：https://www.cnblogs.com/lee454207074/p/11613962.html

文章目錄

• 1.思路解釋
• 2.代碼及注釋

1.思路解釋

• 借子彈：就是比如我給前i-1列配置設定了j-p顆子彈，給第i列配置設定了p顆子彈，但是實際上由于Y磚塊的存在，我可以讓前i-1列借幾顆（記為x）子彈給第i列，這樣第i列就可以用p+x顆子彈了，然後我一直打第i列的磚塊，打完這p+x顆子彈後，由于打到了一些Y磚塊，是以就還剩x顆子彈，然後再還給前i-1列

• s_image[i][cnt]

  ：用cnt顆子彈（包括從其它列借子彈，還子彈，但是總的子彈消耗數還是cnt）射第i列的磚塊可以獲得的最大分數

• s_reality[i][cnt]

  ：用cnt顆子彈（沒有從其它列借子彈）射第i列的磚塊可以獲得的最大分數

• f_image[i][j]

  ：對前i列磚塊用了j顆子彈（包括向後面的列借子彈，還子彈，但是總的子彈消耗數還是j）可以獲得的最大分數

• f_reality[i][j]

  ：對前i列磚塊用了j顆子彈（但是沒有向後面的列借子彈）可以獲得的最大分數

2.代碼及注釋

#include <bits/stdc++.h>

using namespace std;

const int maxn=205;

int s_image[maxn][maxn],s_reality[maxn][maxn];
int f_image[maxn][maxn],f_reality[maxn][maxn];
int visit[maxn][maxn];
int score[maxn][maxn];
int n,m,k;
char c[3];

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d%s",&score[i][j],c);
            if(c[0]=='Y')
                visit[i][j]=1;
        }
    }

    //計算s_i和s_r
    for(int i=1;i<=m;i++){
        //cnt表示實際用的子彈個數
        int cnt=0;
        for(int j=n;j>=1;j--){
            if(visit[j][i])
                s_image[i][cnt]+=score[j][i];
            else{
                cnt++;
                s_image[i][cnt]=s_image[i][cnt-1]+score[j][i];
                s_reality[i][cnt]=s_image[i][cnt-1]+score[j][i];
            }
        }
    }

    for(int i=1;i<=m;i++){
        for(int j=0;j<=k;j++){
            //p表示第i列可以用p顆子彈
            for(int p=0;p<=j&&p<=n;p++){
            //這個循環的意思是，給第i列配置設定p顆子彈，給前i-1列配置設定j-p顆子彈
                f_image[i][j]=max(f_image[i][j],f_image[i-1][j-p]+s_image[i][p]);
                if(p){
                    //如果p>=1，那麼第i列可以借一些子彈給前i-1列
                    f_reality[i][j]=max(f_reality[i][j],f_image[i-1][j-p]+s_reality[i][p]);
                }
                if(j-p){
                    //如果j-p>=1，那麼前i-1列可以借一些子彈給第i列
                    f_reality[i][j]=max(f_reality[i][j],f_reality[i-1][j-p]+s_image[i][p]);
                }
            }
        }
    }

    printf("%d",f_reality[m][k]);
}