2 条题解

  • 1
    @ 2024-12-17 13:31:23
    #include<cstdio>
    struct int128{
        long long hig;
        long long low;
    };
    int n,m;
    long long p=1e18;
    int128 ans,f[85][85][85],a[85][85];
    int128 max(int128 a,int128 b)
    	if(a.hig>b.hig) return a;
    	if(a.hig<b.hig) return b;
    	if(a.low>b.low) return a;
    	if(a.low<b.low) return b;
    	return a;
    }
    int128 operator + (int128 a,int128 b){
        int128 k;
        k.low=0,k.hig=0;
        k.low=a.low+b.low;
        k.hig=k.low/p+a.hig+b.hig;
        k.low%=p;
        return k;
    }
    int128 operator * (int128 a,int b){
    	int128 k;
    	k.low=0,k.hig=0;
    	k.low=a.low*b;
    	k.hig+=k.low/p+b*a.hig;
    	k.low%=p;
    	return k;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j].low);
    	for(int i=1;i<=n;i++)
        for(int len=0;len<m;len++)
        for(int l=1;l+len<=m;l++)
                f[l][l+len][i]=max(f[l+1][l+len][i]+a[i][l],f[l][l+len-1][i]+a[i][l+len])*2;
        for(int i=1;i<=n;i++)
        	ans=ans+f[1][m][i];
        if(ans.hig==0)	printf("%lld",ans.low);
        else	printf("%lld%018lld\n",ans.hig,ans.low);
    }
    
  • 0
    @ 2023-7-19 7:42:08
    #include <iostream>
    #include <cstring>
    #define int __int128 // 定义宏,将int类型替换为__int128类型
    using namespace std;
    
    const int N = 1e2; // 定义常量N为100,表示数组的大小
    int n, m; // 输入的行数和列数
    int a[N][N]; // 存储输入的二维数组
    int dp[N][N]; // 动态规划数组
    int p[100]; // 存储2的幂次方值,最多存储m个幂次方
    int ans = 0; // 最终结果
    
    // 读取输入的整数
    int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9'){
            if(ch == '-')
                f = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9'){
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * f;
    }
    
    // 输出整数
    void print(int x){
        if(x < 0){
            putchar('-');
            x = -x;
        }
        if(x > 9)
            print(x / 10);
        putchar(x % 10 + '0');
    }
    
    signed main()
    {
        n = read(); // 读取行数
        m = read(); // 读取列数
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                a[i][j] = read(); // 读取二维数组
    
        p[0] = 1; // 初始化p[0]为1
        for(int i = 1; i <= m; i++) p[i] = p[i - 1] * 2; // 计算2的幂次方,存储在数组p中
    
        for(int k = 1; k <= n; k++) // 对每一行进行处理
        {
            memset(dp, 0, sizeof(dp)); // 初始化dp数组为0
            for(int i = 1; i <= m; i++)
                for(int j = m; j >= i; j--)
                {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[k][i - 1] * p[m - j + i - 1]); // 更新dp数组
                    dp[i][j] = max(dp[i][j], dp[i][j + 1] + a[k][j + 1] * p[m - j + i - 1]); // 更新dp数组
                }
            int maxn = -1; // 每一行的最大值
            for(int i = 1; i <= m; i++)
            {
                maxn = max(maxn, dp[i][i] + a[k][i] * p[m]); // 更新最大值
            }
            ans += maxn; // 累加结果
        }
        print(ans); // 输出结果
        return 0;
    }
    
    • 1

    信息

    ID
    471
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    19
    已通过
    6
    上传者