• 洛谷千题详解 | P1005 [NOIP2007 提高组] 矩阵取数游戏【C++、 Java、Python语言】


    博主主页:Yu·仙笙

     

    专栏地址:洛谷千题详解

    目录

     题目描述

    输入格式

    输出格式

    输入输出样例

    解析: 

    C++源码:

    Java源码:

    Python源码: 


    ------------------------------------------------------------------------------------------------------------------------------- 

    -------------------------------------------------------------------------------------------------------------------------------  

     题目描述

    帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n×m 的矩阵,矩阵中的每个元素 ai,j​ 均为非负整数。游戏规则如下:

    1. 每次取数时须从每行各取走一个元素,共 n 个。经过 m 次后取完矩阵内所有元素;
    2. 每次取走的各个元素只能是该元素所在行的行首或行尾;
    3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值 ×2i,其中 i 表示第 i 次取数(从 1 开始编号);
    4. 游戏结束总得分为 mm 次取数得分之和。

    帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

    -------------------------------------------------------------------------------------------------------------------------------  

    输入格式

    输入文件包括 n+1 行:

    第一行为两个用空格隔开的整数 n 和 m。

    第 2∼n+1 行为 n×m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。

    -------------------------------------------------------------------------------------------------------------------------------  

    输出格式

    输出文件仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。

    -------------------------------------------------------------------------------------------------------------------------------  

    输入输出样例

    输入 #1

    2 3
    1 2 3
    3 4 2
    

    输出 #1

    82

    -------------------------------------------------------------------------------------------------------------------------------  

    解析: 

    求n行最大得分和,每一行取数又不会影响到其他行,那么只要确保每一行得分最大,管好自家孩子就行了。(这个在动规中叫最优子结构)

    每次取数是在边缘取,那么每次取数完剩下来的元素一定是在一个完整的一个区间中,又是求最优解,区间DP应运而生。

    -------------------------------------------------------------------------------------------------------------------------------  

    C++源码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. const int MAXN = 85, Mod = 10000; //高精四位压缩大法好
    8. int n, m;
    9. int ar[MAXN];
    10. struct HP {
    11. int p[505], len;
    12. HP() {
    13. memset(p, 0, sizeof p);
    14. len = 0;
    15. } //这是构造函数,用于直接创建一个高精度变量
    16. void print() {
    17. printf("%d", p[len]);
    18. for (int i = len - 1; i > 0; i--) {
    19. if (p[i] == 0) {
    20. printf("0000");
    21. continue;
    22. }
    23. for (int k = 10; k * p[i] < Mod; k *= 10)
    24. printf("0");
    25. printf("%d", p[i]);
    26. }
    27. } //四位压缩的输出
    28. } f[MAXN][MAXN], base[MAXN], ans;
    29. HP operator + (const HP &a, const HP &b) {
    30. HP c; c.len = max(a.len, b.len); int x = 0;
    31. for (int i = 1; i <= c.len; i++) {
    32. c.p[i] = a.p[i] + b.p[i] + x;
    33. x = c.p[i] / Mod;
    34. c.p[i] %= Mod;
    35. }
    36. if (x > 0)
    37. c.p[++c.len] = x;
    38. return c;
    39. } //高精+高精
    40. HP operator * (const HP &a, const int &b) {
    41. HP c; c.len = a.len; int x = 0;
    42. for (int i = 1; i <= c.len; i++) {
    43. c.p[i] = a.p[i] * b + x;
    44. x = c.p[i] / Mod;
    45. c.p[i] %= Mod;
    46. }
    47. while (x > 0)
    48. c.p[++c.len] = x % Mod, x /= Mod;
    49. return c;
    50. } //高精*单精
    51. HP max(const HP &a, const HP &b) {
    52. if (a.len > b.len)
    53. return a;
    54. else if (a.len < b.len)
    55. return b;
    56. for (int i = a.len; i > 0; i--)
    57. if (a.p[i] > b.p[i])
    58. return a;
    59. else if (a.p[i] < b.p[i])
    60. return b;
    61. return a;
    62. } //比较取最大值
    63. void BaseTwo() {
    64. base[0].p[1] = 1, base[0].len = 1;
    65. for (int i = 1; i <= m + 2; i++){ //这里是m! m! m! 我TM写成n调了n年...
    66. base[i] = base[i - 1] * 2;
    67. }
    68. } //预处理出2的幂
    69. int main(void) {
    70. scanf("%d%d", &n, &m);
    71. BaseTwo();
    72. while (n--) {
    73. memset(f, 0, sizeof f);
    74. for (int i = 1; i <= m; i++)
    75. scanf("%d", &ar[i]);
    76. for (int i = 1; i <= m; i++)
    77. for (int j = m; j >= i; j--) { //因为终值是小区间,DP自然就从大区间开始
    78. f[i][j] = max(f[i][j], f[i - 1][j] + base[m - j + i - 1] * ar[i - 1]);
    79. f[i][j] = max(f[i][j], f[i][j + 1] + base[m - j + i - 1] * ar[j + 1]);
    80. } //用结构体重载运算符写起来比较自然
    81. HP Max;
    82. for (int i = 1; i <= m; i++)
    83. Max = max(Max, f[i][i] + base[m] * ar[i]);
    84. ans = ans + Max; //记录到总答案中
    85. }
    86. ans.print(); //输出
    87. return 0;
    88. }

    -------------------------------------------------------------------------------------------------------------------------------  

    Java源码:

    1. import java.math.BigInteger;
    2. import java.util.Scanner;
    3. public class Main {
    4. static int [] mp = new int[100];
    5. static BigInteger [] pow = new BigInteger[160];
    6. @SuppressWarnings("resource")
    7. public static void main(String[] args) {
    8. pow[0] = BigInteger.ONE;
    9. pow[1] = BigInteger.valueOf(2);
    10. for(int i = 2; i < 160; i++) {
    11. pow[i] = pow[1].pow(i);
    12. }
    13. Scanner cin = new Scanner(System.in);
    14. BigInteger ans = BigInteger.ZERO;
    15. int n=cin.nextInt(), m=cin.nextInt();
    16. for(int t = 1; t <= n; t++) {
    17. BigInteger [][] f = new BigInteger[100][100];
    18. BigInteger max = BigInteger.ZERO;
    19. for(int j = 1; j <= m; j++)
    20. mp[j]=cin.nextInt();
    21. for(int i = 0; i < 100; i++)
    22. for(int j = 0; j < 100; j++)
    23. f[i][j] = BigInteger.ZERO;
    24. for(int i = 1; i <= m; i++)
    25. for(int j = m; j > 0; j--) {
    26. f[i][j] = f[i][j].max(f[i - 1][j].add(pow[m - j + i - 1].multiply(BigInteger.valueOf(mp[i - 1]))));
    27. f[i][j] = f[i][j].max(f[i][j + 1].add(pow[m - j + i - 1].multiply(BigInteger.valueOf(mp[j + 1]))));
    28. }
    29. for(int i = 1; i <= m; i++)
    30. max = max.max(f[i][i].add(pow[m].multiply(BigInteger.valueOf(mp[i]))));
    31. ans = ans.add(max);
    32. }
    33. System.out.println(ans);
    34. }
    35. }

    -------------------------------------------------------------------------------------------------------------------------------  

    Python源码: 

    1. matrix=[]
    2. n,m=input().split()
    3. n,m=int(n),int(m)
    4. for i in range(n):
    5. row=input().split()
    6. row=[0]+[int(count)for count in row]+[0]
    7. #print(row)
    8. # 把列表塞到列表里形成二维列表
    9. matrix.append(row)
    10. a=[1]#a[0]=1初始化为1
    11. #求到2^m
    12. for i in range(m):
    13. a.append(a[i]*2)
    14. #print(a)
    15. ans=0
    16. for i in range(n):
    17. row=matrix[i]
    18. w=1
    19. #分配一个大小为m+2 * m+2的二维数组
    20. dp=[[0]*(m+2)]*(m+2)
    21. #print(dp)
    22. for st in range(1,m+1):
    23. for ed in range(m,0,-1):
    24. if ed
    25. continue
    26. dp[st][ed]=max(dp[st-1][ed]+row[st-1]*a[m-ed+st-1],dp[st][ed+1]+row[ed+1]*a[m-ed+st-1])
    27. ans+=max([dp[i][i]+row[i]*a[m]for i in range(1,m+1)])
    28. print(ans)

    -------------------------------------------------------------------------------------------------------------------------------  

  • 相关阅读:
    Python学习:len() 函数详解:获取字符串长度或字节数、join()方法:合并字符串
    学习mapster的基本用法
    工作中规范使用Java集合
    如何实现IP地址精准定位?
    若依前后端分离版:增加新的登录接口,用于小程序或者APP获取token,并使用若依的验证方法
    聚观早报|歌尔股份辟谣被苹果砍单;扎克伯格承认因失误裁员
    CSDN编程竞赛第八期 | 参赛经历分享
    iOS重签名-超详细,附排错
    【JS函数】JS函数之高阶函数、组合函数、函数柯里化
    JavaEE+springboot教学仪器设备管理系统o9b00-springmvc
  • 原文地址:https://blog.csdn.net/djfihhfs/article/details/127638102