首页 > 代码库 > BZOJ 2101 DP+优化
BZOJ 2101 DP+优化
思路：
http://www.cnblogs.com/exponent/archive/2011/08/14/2137849.html
f[i,i+len]=sum[i,i+len]-min(f[i+1,i+len],f[i,i+len-1]);
但题目把n出到5000,内存卡到64M,二维的状态存不下..
其实,j这一维可以省掉.我们换个状态表示
f[i,i+len]=sum[i,i+len]-min(f[i+1,i+len],f[i,i+len-1])
然后循环这样写:
for len=1 to n
for i=1 to n-len.
容易看出第二维可以省掉了.
想了好久才懂...
最一开始的DP都没想到TAT
//By SiriusRen#include <cstdio>#include <algorithm>using namespace std;const int N=5555;int n,a[N],sum[N],f[N];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; for(int l=0;l<=n;l++) for(int i=1;i+l<=n;i++) f[i]=sum[i+l]-sum[i-1]-min(f[i],f[i+1]); printf("%d\n",f[1]);}
BZOJ 2101 DP+优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。