luogu 1070 道路游戏

S1

这是我这几天做的第五道普及组第四题（前四道崩了三个），第三道DP（前两个全崩）。
感觉药丸啊。
刚看到这道题的时候，想法大概是需要用三重循环，之后最外面的是时间，然后里面是节点和步数，一开始想用二维DP，后来发现因为是环形道路所以不能这么做，所以只有一维时间。

S2

然后这题大体的思路极其暴力，可以说是没有思考过程秒出，然而大脑当机的我固执地认为秒出的想法肯定有漏洞，又死活找不出来，活活想了半天，然后看了zyc的AC代码，发现我真是想复杂了…… 这个题大概最难的地方就是对place和money的处理了吧，只需要一个累加一个递减加特判就行了。

代码

#include<iostream>
using namespace std;
int n,m,p,dis[1001][1001];
int f[1001],rob[1001],money;
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=m;i++)
        f[i]=-99999;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>dis[i][j];
    for(int i=1;i<=n;i++)
        cin>>rob[i];
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int place=j;
            money=dis[j][i];
            for(int k=1;k<=p;k++)
            {
                if(k>i) break;
                f[i]=max(f[i],f[i-k]+money-rob[place]);
                place--;
				        if(!place) place=n;
                money+=dis[place][i-k];
            }
        }
    }
    cout<<f[m];
}