次元传送门：洛谷P1070
思路
一开始以为要用什么玄学优化 没想到O3就可以过了
我们只需要设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,-,sizeof(f));
cin>>n>>m>>p;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) cin>>load[i][j];
for(int i=;i<=n;i++) cin>>cost[i];
f[]=;//初始化
for(int i=;i<=m;i++)//枚举时间
for(int j=;j<=n;j++)//枚举道路
{
int now=j-;//从第几个工厂走来
if(!now) now=n;//判断环
int val=load[now][i];//记录路上总金币
for(int k=;k<=p;k++)//枚举步数
{
if(i-k<) 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];
}