令f[i][j]表示将i∼j全部取完的最大分数,那么我的方程是:
f[i][j]=max(f[i+1][j]+a[i]×2j−i+1,f[i][j−1]+a[j]×2j−i+1)
代码如下
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int n,m,a[N],f[N][N],ans;
int qpow(int a,int p){
int tmp=1;
while(p){
if(p&1) tmp*=a;
a*=a;
p>>=1;
}
return tmp;
}
int main(){
cin>>n>>m;
while(n--){
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=m;i++) f[i][i]=2*a[i];
for(int l=2;l<=m;l++){
for(int i=1;i+l-1<=m;i++){
int j=i+l-1;
f[i][j]=max(f[i+1][j]+a[i]*qpow(2,l),f[i][j-1]+a[j]*qpow(2,l));
}
}
ans+=f[1][m];
}
cout<<ans;
return 0;
}
还没打高精度,到底是哪里错了