2 条题解

  • 0
    @ 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
      上传者