社区讨论
求dalao指教
P1005[NOIP 2007 提高组] 矩阵取数游戏参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo117il1
- 此快照首次捕获于
- 2023/10/22 13:31 2 年前
- 此快照最后确认于
- 2023/11/02 13:03 2 年前
10分代码,高精度没啥问题用很多次了
动规代码哪里错了qwq
CPP#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct lon{
int l;
char x[101];
lon(){
memset(this,0,sizeof(lon));
l=1;
}
void in(){
char t;
l=0;
do{
t=getchar();
}while(t<'0'||t>'9');
while(t>='0'&&t<='9'){
l++;
x[l]=t-'0';
t=getchar();
}
for(int i=1;i<=l>>1;i++){
swap(x[i],x[l-i+1]);
}
return ;
}
void out(){
for(int i=l;i>=1;i--){
printf("%d",x[i]);
}
return ;
}
};
lon maxof(lon x,lon y){
for(int i=max(x.l,y.l);i>=1;i--){
if(x.x[i]>y.x[i])return x;
if(x.x[i]<y.x[i])return y;
}
return x;
}
lon add(lon x,lon y){
lon ans;
int l=ans.l=max(x.l,y.l);
for(int i=1;i<=l;i++){
ans.x[i]+=x.x[i]+y.x[i];
ans.x[i+1]+=ans.x[i]/10;
ans.x[i]%=10;
}
if(ans.x[l+1])ans.l++;
return ans;
}
lon mult(lon x,lon y){
lon ans;
ans.l=x.l+y.l-1;
for(int i=1;i<=x.l;i++){
for(int j=1;j<=y.l;j++){
ans.x[i+j-1]+=x.x[i]*y.x[j];
ans.x[i+j]+=ans.x[i+j-1]/10;
ans.x[i+j-1]%=10;
}
}
while(ans.x[ans.l+1]){
ans.l++;
}
return ans;
}
lon con[81];
int n,m;
lon ans;
void find(){
lon arr[81];
lon dp[81][81];
for(int i=1;i<=m;i++)
arr[i].in();
for(int i=1;i<m;i++){
for(int j=m;j>i;j--){
dp[i+1][j]=maxof(dp[i+1][j],add(dp[i][j],mult(con[i+m-j+1],arr[i])));
dp[i][j-1]=maxof(dp[i][j-1],add(dp[i][j],mult(con[i+m-j+1],arr[j])));
}
}
lon tmp;
for(int i=1;i<=m;i++){
tmp=maxof(tmp,dp[i][i]);
}
ans=add(ans,tmp);
// tmp.out();
// printf("\n");
return ;
}
int main(){
scanf("%d%d",&n,&m);
con[1].x[1]=2;
for(int i=2;i<=m+1;i++)
con[i]=mult(con[i-1],con[1]);
for(int i=1;i<=n;i++)
find();
ans.out();
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...