洛谷P1174 打磚塊——動态規劃-背包

動态規劃O（nmk）

一、定義兩個輔助數組 dn【i】【j】和 dy【i】【j】

dn【i】【j】 表示在第 i 列打 j 槍最後一槍打在 N 上所得分數

dy【i】【j】 表示在第 i 列打 j 槍最後一槍打在 Y 上所得分數

二、再定義兩個狀态轉移數組 dpn【i】【j】和 dpy【i】【j】

dpn【i】【j】 表示在前 i 列打 j 槍最後一槍打在 N 上所得最大分數

dpy【i】【j】 表示在前 i 列打 j 槍最後一槍打在 Y 上所得最大分數

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn= 2e5+5;

int n,m,k;
bool tp[210][210];
int val[210][210];
int dy[210][210],dn[210][210];
int dpy[210][210],dpn[210][210];

void solve()
{
	cin>>n>>m>>k;
	char c;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		cin>>val[i][j]>>c;
		tp[i][j] = (c=='Y');
	}
	
	/*
	dn[i][j] : 第i列消耗j，且最後打在no上
	dy[i][j] : 第i列消耗j，且最後打在yes上
	*/
	for(int j=1;j<=m;j++)
	{
		int cnt=0;
		for(int i=n;i>=1;i--)
		{
			if(tp[i][j]) dy[j][cnt] += val[i][j];
			else
			{
				int v = dy[j][cnt] + val[i][j];
				dn[j][cnt+1] = dy[j][cnt+1] = v;
				cnt++;
			}
		}
	}
	/*
	dpn[i][j] : 前i列共消耗j，且最後打在no上
	dpy[i][j] : 前i列共消耗j，且最後打在yes上
	
	dpy[i][a] = max( dpy[i-1][a-b] + dy[i][b] )
	前i列共消耗a發最後打在yes上 
		== 前i-1列共消耗a-b發最後打在yes上 + 第i列消耗b發最後打在yes上
	
	前i列共消耗a發最後打在no上
		=> 這發no要麼在前i-1列上，要麼在第i列上
	*/
	for(int i=1;i<=m;i++)
	{
		for(int a=0;a<=k;a++)	//前i列消耗a
		{
			for(int b=0;b<=min(a,n);b++)	//第i列消耗b
			{
				dpy[i][a] = max(dpy[i][a], dpy[i-1][a-b] + dy[i][b]);
				if(b!=0)
					dpn[i][a] = max(dpn[i][a], dpy[i-1][a-b] + dn[i][b]);
				if(a!=b)
					dpn[i][a] = max(dpn[i][a], dpn[i-1][a-b] + dy[i][b]);
			}
		}
	}
	
	cout<<dpn[m][k]<<endl;
}
int main()
{
	IOS;
//	int _;cin>>_;while(_--)
	solve();return 0;
}