安装了lnmp怎么做网站,网站首页策划怎么做,学校网站类型,微信无法登录wordpress转跳P1005
题目描述 帅帅经常跟同学玩一个矩阵取数游戏#xff1a;对于一个给定的 n \times mnm 的矩阵#xff0c;矩阵中的每个元素 a_{i,j}a i,j 均为非负整数。游戏规则如下#xff1a;
每次取数时须从每行各取走一个元素#xff0c;共 nn 个。经过 mm 次后取完矩…转跳P1005
题目描述 帅帅经常跟同学玩一个矩阵取数游戏对于一个给定的 n \times mn×m 的矩阵矩阵中的每个元素 a_{i,j}a i,j 均为非负整数。游戏规则如下
每次取数时须从每行各取走一个元素共 nn 个。经过 mm 次后取完矩阵内所有元素 每次取走的各个元素只能是该元素所在行的行首或行尾 每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值 \times 2^i×2 i 其中 ii 表示第 ii 次取数从 11 开始编号 游戏结束总得分为 mm 次取数得分之和。 帅帅想请你帮忙写一个程序对于任意矩阵可以求出取数后的最大得分。
输入格式 输入文件包括 n1n1 行
第一行为两个用空格隔开的整数 nn 和 mm。
第 2\backsim n12∽n1 行为 n \times mn×m 矩阵其中每行有 mm 个用单个空格隔开的非负整数。
输出格式 输出文件仅包含11行为一个整数即输入矩阵取数后的最大得分。
输入输出样例 输入 #1复制 2 3 1 2 3 3 4 2 输出 #1复制 82 说明/提示 NOIP 2007 提高第三题。
数据范围
60%60% 的数据满足1\le n,m\le 301≤n,m≤30答案不超过 10^{16}10 16 。
100%100% 的数据满足1\le n,m\le 801≤n,m≤800\le a_{i,j}\le10000≤a i,j ≤1000。
思路是一个简单dp没啥好说算出没有行的数值加起来就好了。
重点的__int128 的模板
#includebits/stdc.h
#define INF 0x3f3f3f3f3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod1e97;
const ll N 1e6;
const double eps 1e-4;
const double piacos(-1);
ll gcd(int a,int b){return !b?a:gcd(b,a%b);}
__int128 ans0;
__int128 dp[100][100];
int a[100][100];
int n,m;
__int128 p[100];
__int128 dp1(int x)
{FILL(dp,0);for(int i1;im;i){for(int jm;ji;j--){dp[i][j]max(dp[i-1][j]a[x][i-1]*p[m-ji-1],dp[i][j1]a[x][j1]*p[m-ji-1]);}}__int128 ans0;for(int i1;im;i) ansmax(ans,dp[i][i]a[x][i]*p[m]);return ans;
}
void print(__int128 x)
{if(x0) return;if(x9) print(x/10);putchar(x%100);
}
int main(){ioscinnm;p[1]2;for(int i2;i80;i) p[i]p[i-1]*2;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}ansdp1(i);}print(ans);
}
__int128的输入输出模板
inline __int128 read()
{__int128 x 0, f 1;char ch getchar();while (ch 0 || ch9){if (ch -)f -1;ch getchar();}while (ch 0 ch 9){x (x 1) (x 3) (ch - 0);ch getchar();}return x * f;
}
void print(__int128 x)
{if (x 0){putchar(-);x -x;}if (x 9)print(x / 10);putchar(x % 10 0);
}
