【题解】洛谷P1070 道路游戏（线性DP）

次元传送门：洛谷P1070

思路

一开始以为要用什么玄学优化 没想到O³就可以过了

我们只需要设f[i]为到时间i时的最多金币

需要倒着推回去 即当前值可以从某个点来

那么状态转移方程为：

f[i]=max(f[i],f[i-k]+val-cost[now]);

now表示从now这个工厂来

cost表示在now买下了机器人

val为从now走i个单位时间路上可收集的总金币

代码

#include<iostream> #include<cstring> using namespace std; #define maxn 1010 int n,m,p; int load[maxn][maxn],cost[maxn]; int f[maxn]; int main() { memset(f,-127,sizeof(f)); cin>>n>>m>>p; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>load[i][j]; for(int i=1;i<=n;i++) cin>>cost[i]; f[0]=0;//初始化 for(int i=1;i<=m;i++)//枚举时间 for(int j=1;j<=n;j++)//枚举道路 { int now=j-1;//从第几个工厂走来 if(!now) now=n;//判断环 int val=load[now][i];//记录路上总金币 for(int k=1;k<=p;k++)//枚举步数 { if(i-k<0) break;//时间不能为负数 f[i]=max(f[i],f[i-k]+val-cost[now]); now--;//倒推回去 if(!now) now=n; val+=load[now][i-k];//统计路上金币 } } cout<<f[m]; }

 

转载于:https://www.cnblogs.com/BrokenString/p/9914309.html