首页 > 代码库 > BZOJ1915: [Usaco2010 Open]奶牛的跳格子游戏
BZOJ1915: [Usaco2010 Open]奶牛的跳格子游戏
权限题，没有传送门。
这很显然是一道DP题，刚看完题目可能会比较懵逼。这道题如果不要求回去，那么就是一道很裸的DP题。但是本题要求回去而且回去的格子的前一个格必须是之前经过的。
先不考虑回去的路程，对于一段长度在$K$之内的区间，其中的所有值为正数的点都是可以到达的。所以先搞个前缀和:
$sum_i= \sum _{j=1}^i a_j \times [a_j>0]$
这个搞完后如果不算回来的，可以得到以下转移方程：
$f[i]=max \{ f[j]+sum[i-1]-sum[j] \}$
其实到这一步，带上回去的状态转移方程也很显然了。
$f[i]=max \{f[j]+sum[i-2]-sum[j]+a[i]+a[i-1] \}$
表示第$i$个点为去时经过的点且会返回的前一个点，$sum[]$和$f[]$均存在单调性，所以可以用单调队列优化决策单调性，使得总体复杂度降为$O(N)$。
但是$f[i]_{max}$并不是最后的答案，因为对于任意一个点$i$,$[i+1,i-1+K]$都是可以到达的，所以要把这一段对答案的贡献也累加上。
在具体实现时，注意单调队列在DP前应进队0和1，因为第0个点不是必须停留的点。
1 //BZOJ 1915 2 //by Cydiater 3 //2016.10.6 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <queue> 9 #include <cstdio>10 #include <cmath>11 #include <ctime>12 #include <map>13 #include <iomanip>14 #include <cstdlib>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int MAXN=3e6+5;20 const int oo=0x3f3f3f3f;21 inline ll read(){22 char ch=getchar();ll x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 ll N,K,sum[MAXN],a[MAXN],q[MAXN],head,tail,f[MAXN],ans=0;28 namespace solution{29 void init(){30 memset(sum,0,sizeof(sum));31 N=read();K=read();32 up(i,1,N)a[i]=read();33 up(i,1,N)sum[i]=sum[i-1]+(a[i]>0?a[i]:0);34 }35 void DP(){36 head=1;tail=0;q[++tail]=0;q[++tail]=1;37 up(i,2,N){38 while(head<tail&&i-q[head]>K)head++;39 f[i]=f[q[head]]+sum[i-2]-sum[q[head]]+a[i]+a[i-1];40 while(head<tail&&f[i]-f[q[tail]]>sum[i]-sum[q[tail]])tail--;41 q[++tail]=i;42 }43 up(i,1,N)ans=max(ans,f[i]+((i-1+K<=N)?(sum[i-1+K]-sum[i]):(sum[N]-sum[i])));44 }45 void output(){46 cout<<ans<<endl;47 }48 }49 int main(){50 //freopen("input.in","r",stdin);51 using namespace solution;52 init();53 DP();54 output();55 return 0;56 }
BZOJ1915: [Usaco2010 Open]奶牛的跳格子游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。