???为什么开O2就对了,不开就错
查看原帖
???为什么开O2就对了,不开就错
129390
yangwenbin楼主2020/9/13 21:04

为什么开O2就对了,不开就错

求帮忙

#include <bits/stdc++.h>
using namespace std;

const long long SIZE =  250;
const long long low = -0x3f3f3f3f;

inline long long read()
{
	long long x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x;
}

struct node
{
	long long num;
	bool give;
};
node brick[SIZE][SIZE];
long long n,m,k,bottom;
long long cur[SIZE];
long long tot[SIZE][SIZE],sum1[SIZE][SIZE],sum2[SIZE][SIZE];
long long dp[SIZE][SIZE][2];

int main()
{
	n = read();
	m = read();
	k = read();
	for (long long i = n; i >= 1; --i)
	{
		for (long long j = 1; j <= m; ++j)
		{
			brick[i][j].num = read();
			char x;
			scanf("%c",&x);
			brick[i][j].give = ( x == 'Y' ? true : false );
		}
	}
	for (long long i = 1; i <= m; ++i)
	{
		for (long long j = 1; j <= n; ++j)
		{
			if(!brick[j][i].give)
			{
				cur[i] = j - 1;
				break;
			}
			bottom += brick[j][i].num;
		}
	}
	for (long long i = 1; i <= m; ++i)
	{
		for (long long j = cur[i] + 1; j <= n; ++j)
		{
			sum2[i][j] = sum1[i][j] = sum1[i][j-1] + brick[j][i].num;
		} 
	}
	for (long long i = 1; i <= m; ++i)
	{
		tot[i][cur[i] + 1] = 1;
		for (long long j = cur[i] + 1; j <= n;)
		{
			long long indax = j;
			while (brick[indax + 1][i].give)
			{
				indax ++;
			}
			sum2[i][j] += (sum1[i][indax] - sum1[i][j]);
			tot[i][indax + 1] = tot[i][j] + 1;
			j = indax + 1;
		}
	}
	for (long long i = 0; i <= m; ++i)
	{
		dp[i][0][0] = low;
	}
	for (long long i = 1; i <= m; ++i)
	{
		for (long long bullet = 1; bullet <= k; ++bullet)
		{
			dp[i][bullet][0] = dp[i-1][bullet][0];
			dp[i][bullet][1] = dp[i-1][bullet][1];
			for (long long j = cur[j] + 1; j <= n; ++j)
			{
				if (!brick[j][i].give && bullet >= tot[i][j])
				{
					dp[i][bullet][0] = max(dp[i][bullet][0],dp[i-1][bullet-tot[i][j]][1] + sum1[i][j]);
					dp[i][bullet][0] = max(dp[i][bullet][0],dp[i-1][bullet-tot[i][j]][0] + sum2[i][j]);
					dp[i][bullet][1] = max(dp[i][bullet][1],dp[i-1][bullet-tot[i][j]][1] + sum2[i][j]);
				}
			}
		}
	}
	dp[m][k][0] += bottom;
	printf("%lld\n",dp[m][k][0]);
	return 0;
}
2020/9/13 21:04
加载中...