如果有一组数据是4,3,10,1,1,1,1,1,1,1,1,5,5,5,5,9贪心就是错的,会先把5取完,然而应该先取1。
by lizongru @ 2017-08-18 22:59:05
前面的状态对后面有影响,这已经失去了贪心的条件。
by Randle @ 2017-08-20 09:39:00
@ Randle 同意!
by fondness_zzy @ 2017-08-22 14:54:07
dp题目的结构就是决策影响后续但是无后效性
#dp万岁
by yy233 @ 2017-08-28 11:39:56
@[征途者](/space/show?uid=52781) 恩
by a2063436123 @ 2017-09-08 19:16:38
#要是能让你用贪心过了,这题就不会出现在dp这了##滑稽
by dzl666 @ 2017-09-25 00:01:17
*************!*************
by lty2017 @ 2017-10-11 22:59:40
```cpp
# #include<bits/stdc++.h>
# #define lll __int128
#void print(lll x)
#{
# if (x==0) return;
# if (x) print(x/10);
# putchar(x%10+'0');
#}
#int n,m;
#lll ans=0;
#int a[100]={0};
#lll f[100][100];
#lll p[100]={1};
#lll dp()
#{
# memset(f,0,sizeof(f));
# for(int i=1;i<=m;i++)
# {
# for(int j=m;j>=i;j--)
# {
# f[i][j]=std::max( f[i-1][j]+ p[m-j+i-1]*a[i-1] , f[i][j+1]+ p[m-j+i-1]*a[j+1] );
# }
#}
#lll maxn=-1;
#for(int i=1;i<=m;i++) maxn=std::max(maxn,f[i][i]+a[i]*p[m]);
#return maxn;
#}
#int main()
#{
# for(int i=1;i<=90;i++) p[i]=p[i-1]<<1;
# scanf("%d%d",&n,&m);
# for(int i=1;i<=n;i++)
#{
# for(int j=1;j<=m;j++)
# scanf("%d",a+j);
# ans+=dp();
#}
#if(ans==0) puts("0");
# else print(ans);
# return 0;
#}
```
by lty2017 @ 2017-10-11 23:11:29
```cpp
#include<bits/stdc++.h>
#define lll __int128
void print(lll x)
{
if (x==0) return;
if (x) print(x/10);
putchar(x%10+'0');
}
int n,m;
lll ans=0;
int a[100]={0};
lll f[100][100];
lll p[100]={1};
lll dp()
{
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
{
for(int j=m;j>=i;j--)
{
f[i][j]=std::max( f[i-1][j]+ p[m-j+i-1]*a[i-1] , f[i][j+1]+ p[m-j+i-1]*a[j+1] );
}
}
lll maxn=-1;
for(int i=1;i<=m;i++) maxn=std::max(maxn,f[i][i]+a[i]*p[m]);
return maxn;
}
int main()
{
for(int i=1;i<=90;i++) p[i]=p[i-1]<<1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",a+j);
ans+=dp();
}
if(ans==0) puts("0");
else print(ans);
return 0;
}
```
by lty2017 @ 2017-10-11 23:11:57