题目链接
https://www.luogu.org/problemnew/show/P1005
分析
忽然发现这篇题解好像并没有什么意义... 因为跟奶牛 0 食那道题一模一样, 博主比较懒如果您想看题解的话去区间 DP 标签中找奶牛 0 食那道题吧, 实在抱歉...
话说 NOIP 喜欢考奶牛题啊 (e.g. NOIP2017 D1T1),USACO 刷完是不是就能阿克了呀
代码没写高精用__int128 代替, 话说什么时候补个高精的坑 (flag)
代码
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <algorithm>
- #include <cctype>
- #include <queue>
- #define ll __int128
- #define ri register int
- using std::min;
- using std::max;
- template <class T>inline void read(T &x){
- x=0;int ne=0;char c;
- while(!isdigit(c=getchar()))ne=c=='-';
- x=c-48;
- while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+c-48;
- x=ne?-x:x;return ;
- }
- const int maxn=83;
- const ll inf=1e25;
- ll fac[maxn];
- int n,m;
- ll f[maxn][maxn][maxn],g[maxn][maxn];
- void print(ll x){
- if(!x) return;
- if(x) print(x/10);
- putchar(x%10+'0');
- }
- int main(){
- fac[0]=1;
- for(ri i=1;i<=80;i++)fac[i]=fac[i-1]*2;
- read(n),read(m);
- for(ri i=1;i<=n;i++){
- for(ri j=1;j<=m;j++){
- read(g[i][j]);
- f[i][j][j]=g[i][j]*fac[m];
- }
- }
- int l,r;
- for(ri p=1;p<=n;p++){
- for(ri len=2;len<=m;len++){
- for(l=1;l<=m-len+1;l++){
- r=l+len-1;
- f[p][l][r]=max(f[p][l+1][r]+g[p][l]*fac[m-len+1],f[p][l][r-1]+g[p][r]*fac[m-len+1]);
- }
- }
- }
- ll ans=0;
- for(ri i=1;i<=n;i++)ans+=f[i][1][m];
- if(!ans)puts("0");
- else print(ans);
- puts("");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2767953.html