80分代码求调
查看原帖
80分代码求调
958346
xuan_x楼主2023/10/15 11:49
#include <bits/stdc++.h>
#define r (l + len - 1)

using namespace std;

int a[88][88], n, m;
string dp[88][88];

string pow2[88];

string operator * (string s, int k)
{
	int num[10010] = {0}, i;
	string ans;
	int len = s.size();
	for (i = 0; i < len; i++)
	{
		num[len - i] = s[i] - '0';
	}
	num[0] = len;
	for (i = 1; i <= num[0]; i++)
	{
		num[i] *= k;
	}
	for (i = 1; i <= num[0]; i++)
	{
		if (num[i] >= 10)
		{
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	while(num[num[0] + 1])
    {
        num[0]++;
        num[num[0]+1] += num[num[0]]/10;
        num[num[0]]%=10;
    }
	while(num[num[0]]==0 && num[0]!=1) num[0]--;
	for (i = num[0]; i >= 1; i--)
	{
		ans += char(num[i] + '0');
	}
	return ans;
}

string operator + (string s1, string s2)
{
	int i;
	int num1[10010] = {0};
	int num2[10010] = {0};
	int len1 = s1.size();
	int len2 = s2.size();
	for (i = 0; i < len1; i++) num1[len1 - i] = s1[i] - '0';
	for (i = 0; i < len2; i++) num2[len2 - i] = s2[i] - '0';
	int maxlen = max(len1, len2);
	for (i = 1; i <= maxlen; i++)
	{
		num1[i] += num2[i];
		if (num1[i] >= 10)
		{
			num1[i + 1] += num1[i] / 10;
			num1[i] %= 10;
		}
	}
	if (num1[maxlen + 1]) maxlen++;
	string ans;
	for (i = maxlen; i >= 1; i--)
	{
		ans += char(num1[i] + '0');
	}
	return ans;
}

string strmax(string s1, string s2)
{
	int len1 = s1.size();
	int len2 = s2.size();
	if (len1 > len2) return s1;
	if (len1 < len2) return s2;
	return max(s1, s2);
}

int main()
{
	int i, j, len, l, line;
	string maxx = "0", sum = "0";
	pow2[0] = "1";
	for (i = 1; i <= 80; i++)
	{
		pow2[i] = pow2[i - 1] * 2;
	}
	string ans;
    scanf("%d%d",&n,&m);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
            scanf("%d",&a[i][j]);
		}
	}
	swap(n, m);
	for (line = 1; line <= m; line++)
	{
		maxx = "0";
		for( i = 0; i <= n + 1; i++)
		{
			for( j = 0; j <= n + 1; j++)
			{
				dp[i][j] = "0";
			}
		}
		for (len = n - 1; len >= 1; len--)
		{
			for (l = 1; r <= n; l++)
			{
				i = n - len;
				string s1 = "0", s2 = "0";
				if(r + 1 <= n) s1 = dp[l][r + 1] + pow2[i] * a[line][r + 1];
				if(l - 1 >= 1) s2 = dp[l - 1][r] + pow2[i] * a[line][l - 1];
				dp[l][r] = strmax(s1, s2);
				if (l == r)
	    		{
					maxx = strmax(maxx, dp[l][l] + pow2[i + 1] * a[line][l]);
				}
			}
		}
		sum = sum + maxx;
	}
	cout << sum;
	return 0;
}
2023/10/15 11:49
加载中...