RowGame TopCoder - 10664 DP+图论 hqg_ac

$RowGame$ $TopCoder$ $-$ $10664$

题意是在一段区间中，跳k步，向跳之后必须向右跳，

每一步从$a[i]$跳到$a[j]$时会获得$a[i]+...+a[j]$的能量，

跳的过程中不得出现任何时刻<0，求$MAX$

分析:

首先，容易想到结尾时肯定是在某一段区间中跳来跳去刷分。

我们把跳动过程抽象一下

$1 ... a b$ $a b$…… $c d$ $c d$ …..$

为什么会有$ab$这一个环？ 肯定是$ab$ 和$cd$之间有一个巨大的负数，需要在$ab$段刷够分再跳到$cd$段刷分

思路来了：这不就是个裸的 图论+$DP$ 么

$dp$数组被拆分成两部分：$tim[i],val[i]$,分别表示到达i的最小步数和最大分值

预处理出以i为后缀$(j(<=i)~i)$的最大环长（跳过来再跳回去，形成一个正环）$C[i]$

初始的时候$tim$赋$inf,val$赋$-inf$

由于$N$很小，我们通过$Bellman-Ford$的方法解决每一个$dp[]$（同样也可以用$Dijkstra,SPFA$）

处理方法详见代码和注释

之后，统计答案，只要$tim[i]<=K$即可

不要忘记最后一次跳到一个最大的地方刷分！！！

注意答案要$long$ $long$

#include 
using namespace std ;
#define inf ~0ull>>1
#define infs 3LL<<62
long long max(long long a,long long b){return a>b?a:b ;
}
class RowGame{
private:long long tim[110],val[110],C[110] ;long long K;int n,nn;long long a[110],G[110][110] ; //tim[i]:到达i时最少需要多少步 //val[i]:到达i时的最大分 //C[i]:i的后缀和的最大值（To 刷分） 
public:long long score(vector<int> board,int k){K=k; n=board.size() ;nn=2*n;//nn：拆点，记录向左，向右 for (int i=0;ifor (int i=0;ifor (int j=0;jfor (int i=0;ilong long sum=0;for (int j=i;j//累加得到 }} for (int i=0;i//计算最大环长(枚举i前） C[i]=0;for (int j=0;jfor (int i=0;i//初始一个ooval[i]=infs ;//初始一个-oo}tim[0]=val[0]=0;for (int rnd=0;rnd//类似Bellman-Ford for (int i=0;iif (tim[i]!=inf){for (int j=0;jif (G[i][j]!=infs){long long t=tim[i],v=val[i] ;if (v+G[i][j]<0) { //跳过这段出现负数，需要刷分 if (C[i]<=0) continue ;//并没有起到任何的刷分效果（因为它是负的）long long u=(-(v+G[i][j])+C[i]-1)/C[i] ;//上取整，u表示在i~j这段区间中最少要刷多少回才能跳到下一个地方t+=u*2 ;//+刷分的时间 v+=u*C[i] ;//刷得的分 }v+=G[i][j] ;t++;//还有一次机会，选一个最佳的 if (tval[j])){tim[j]=t;val[j]=v ;//时间更优或者值更大 }} }} long long ans=0;for (int i=0;iif (tim[i]<=K){ans=max(ans,val[i]);ans=max(ans,val[i]+(K-tim[i])/2*C[i]) ;//可以选择当前最大值，或者在这个最大环中刷分 if (tim[i]!=K){for (int j=0;jif (G[i][j]!=infs){ans=max(ans,val[i]+(K-1-tim[i])/2*C[i]+G[i][j]) ;//在最大环上刷分，不要忘记最后一轮再找一个最大位置刷一下 }}} }} return ans ;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！