关键词:
和奶牛那个题很像,每一行状态互不影响,也就是求 n 遍DP
不过高精度非常恶心,第一次写,调了我一上午。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 struct Big_int 6 { 7 int s[35], idx; 8 Big_int() 9 { 10 idx = 0; 11 memset(s, 0, sizeof(s)); 12 } 13 }; 14 15 int n, m; 16 Big_int ans, a[81], f[81][81]; 17 18 inline void clear(Big_int &x) 19 { 20 x.idx = 0; 21 memset(x.s, 0, sizeof(x.s)); 22 } 23 24 inline Big_int Big(int x) 25 { 26 Big_int ret; 27 while(x) 28 { 29 ret.s[ret.idx] = x % 10; 30 x /= 10; 31 ret.idx++; 32 } 33 return ret; 34 } 35 36 inline bool operator > (const Big_int x, const Big_int y) 37 { 38 int i; 39 if(x.idx > y.idx) return 1; 40 else if(x.idx < y.idx) return 0; 41 else for(i = x.idx - 1; i >= 0; i--) 42 if(x.s[i] > y.s[i]) return 1; 43 else if(x.s[i] < y.s[i]) return 0; 44 } 45 46 inline Big_int Max(const Big_int x, const Big_int y) 47 { 48 return x > y ? x : y; 49 } 50 51 inline int max(int x, int y) 52 { 53 return x > y ? x : y; 54 } 55 56 inline Big_int operator + (const Big_int x, const Big_int y) 57 { 58 int i; 59 Big_int ret; 60 ret.idx = max(x.idx, y.idx) + 1; 61 for(i = 0; i < ret.idx; i++) 62 { 63 ret.s[i] += x.s[i] + y.s[i]; 64 ret.s[i + 1] += ret.s[i] / 10; 65 ret.s[i] %= 10; 66 } 67 while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--; 68 return ret; 69 } 70 71 inline Big_int operator * (const Big_int x, const Big_int y) 72 { 73 int i, j; 74 Big_int ret; 75 ret.idx = x.idx + y.idx; 76 for(i = 0; i < x.idx; i++) 77 for(j = 0; j < y.idx; j++) 78 { 79 ret.s[i + j] += x.s[i] * y.s[j]; 80 ret.s[i + j + 1] += ret.s[i + j] / 10; 81 ret.s[i + j] %= 10; 82 } 83 while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--; 84 return ret; 85 } 86 87 inline void print(const Big_int x) 88 { 89 int i; 90 if(!x.idx) printf("0"); 91 else for(i = x.idx - 1; i >= 0; i--) printf("%d", x.s[i]); 92 puts(""); 93 } 94 95 inline int read() 96 { 97 int x = 0, f = 1; 98 char ch = getchar(); 99 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 100 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 101 return x * f; 102 } 103 104 inline Big_int dp(int x, int y, Big_int z) 105 { 106 if(f[x][y].idx) return f[x][y]; 107 if(x == y) return f[x][y] = a[x] * z; 108 else return f[x][y] = Max(dp(x + 1, y, z * Big(2)) + a[x] * z, dp(x, y - 1, z * Big(2)) + a[y] * z); 109 } 110 111 int main() 112 { 113 int i, j; 114 n = read(); 115 m = read(); 116 while(n--) 117 { 118 for(i = 1; i <= m; i++) a[i] = Big(read()); 119 for(i = 1; i <= m; i++) 120 for(j = 1; j <= m; j++) 121 clear(f[i][j]); 122 ans = ans + dp(1, m, Big(2)); 123 } 124 print(ans); 125 return 0; 126 }
luogup1005矩阵取数游戏区间dp(代码片段)
...x(dp[i+1][j]+2^(m-(j-l))*mp[t][i],dp[i][j-1]+2^(m-(j-l))*mp[t][j])不想写高精度,python水一发。1n,m=map(int,input().split())2res=03mp=[[0foriinrange(0,80,1)]foriinrange(0,80,1)]4dp=[[-1foriinrange(0,80,1)]foriinrange(0,80,1)]5defdfs(t,l,r):6if(dp[l][r]>=0):7returndp[l][r]8if(l==r):9dp[l... 查看详情
dp+高精度(洛谷1005矩阵取数游戏noip2007提高第三题)
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取走的各个元素只能是该元素... 查看详情
18.7.27luogup1005矩阵取数游戏(代码片段)
题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n imesmn×m 的矩阵,矩阵中的每个元素 a_i,jai,j? 均为非负整数。游戏规则如下:每次取数时须从每行各取走一个元素,共 nn 个。经过 mm... 查看详情
p1005矩阵取数游戏(代码片段)
P1005矩阵取数游戏高精度真好van假的#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;structnode//高精度结构体intlen;intbase[101];voidfill(intval)//初始化函数,每次写高 查看详情
ac日记——矩阵取数游戏洛谷p1005
矩阵取数游戏 思路: dp+高精; 代码:#include<bits/stdc++.h>usingnamespacestd;#definelllonglongstructInt{intlen;charai[300];Int(){len=1,ai[0]=0;}voidCount(intpos){len++;if(pos/10)Count(pos/10);}voido 查看详情
tyvj矩阵取数label:高精度+dp
题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取走的各个元素只能... 查看详情
dp算法第二发之noip矩阵取数游戏
dp+高精度。希望通过此题了解高精度。 矩阵取数游戏(game.pas/c/cpp)【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:每次取... 查看详情
p1005矩阵取数游戏(60)
...https://www.luogu.org/problem/show?pid=1005题目大意:有一个n*m的矩阵,玩一个取数游戏,每次从1到n行取行首或行尾乘2的取的次数次方为这次取数的得分,求得分最大值。 A:每次取每行最大不就行了?定义f[i][j]为取到第i次,到第j行... 查看详情
codevs1166矩阵取数游戏
二次联通门: codevs1166矩阵取数游戏 /*codevs1166矩阵取数游戏SB区间dpdp[l][r]=max(dp[l+1][r]+number[l],dp[l][r-1]+number[r])*2;不过要套高精我用的高精是全部封装好的可以像平时的int等类型用缺点就是慢。。。慢差不多1/3... 查看详情
p1005矩阵取数游戏
P1005矩阵取数游戏题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取... 查看详情
洛谷p1005矩阵取数游戏
P1005矩阵取数游戏题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取... 查看详情
洛谷p1005矩阵取数游戏
P1005矩阵取数游戏题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取... 查看详情
洛谷1005矩阵取数游戏
Description帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取走的各个元素只能... 查看详情
p1005矩阵取数游戏
题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取走的各个元素只能... 查看详情
洛谷p1005矩阵取数游戏
题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取走的各个元素只能... 查看详情
矩阵取数游戏洛谷p1005
题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.每次取走的各个元素只能... 查看详情
p1005矩阵取数游戏(代码片段)
题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下: 1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素; 2.每次取走的各个... 查看详情
洛谷p1005矩阵取数游戏题解
...w.luogu.org/problem/show?pid=1005题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;2.... 查看详情