题解 P1717 【钓鱼】

· · 题解

好的这里是一个第一次写题解的蒟蒻

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,l,ans;
int b[110],t[110],a[110][1010],f[110][1010];
int main()
{
    ios::sync_with_stdio(false);
    //由于读优太长所以打的cincout蒟蒻加速代码
    cin>>n; memset(f,128,sizeof(f));
    //因为有小可爱问就补充一下w
    //f数组初始化为-2139062144的原因是因为
    //f[i][j]表示走到第i个池塘花费j个单位时间获得的最大鱼数
    //但是我们可能没有办法在第j个单位时间的时候到达第i个池塘
    //如果f[i][j]=0 那么当f[i][j]+a[i][k]的时候就会顺理成章的钓到鱼了啊喂!!!
    // (意念钓鱼也太可怕了叭orz 
    //所以其实就相当于多开了一个数组判断是否能到达
    //那么这个时候赋为极小值就一定不会被+a[i][k]给加回正数
    //那么在max()判断的时候就会是0啦
    //如果不加初始化了话答案就会比标准答案大
    //这样解释可以懂吗23333 
    for (i=1;i<=n;i++) cin>>a[i][1];
    for (i=1;i<=n;i++)
    {
        cin>>j; b[i]=1; k=a[i][1];
        while (k-j>0) 
            k=k-j,a[i][++b[i]]=a[i][b[i]-1]+k;
        //这段就是改动 先把鱼塘之间的时间差算好
    }
    for (i=2;i<=n;i++) cin>>t[i];
    cin>>m; f[0][0]=0;
    for (i=1,l=t[i];i<=n&&l<=m;i++,l+=t[i])
    for (j=l;j<=m;j++)
    {
        for (k=0;k<=b[i]&&k+t[i]<=j;k++)
            f[i][j]=max(f[i][j],f[i-1][j-k-t[i]]+a[i][k]);
        //其实主要区别就在于a[i][k]在上面事先被预处理了
        //而另一个程序是在下面直接算的...
        //然而我并找不出来直接算的错误在哪里
        ans=max(ans,f[i][j]);
    }
    cout<<ans;
    return 0;
}

蒟蒻的代码略丑不要嫌弃啊(。・・)ノ

评论区有质疑代码过不去的请看清钓鱼的读入格式

本程是鱼塘钓鱼正解 与钓鱼读入格式有出入

但这种程度的差异 基本的判断是一个OIer必备可能有?的能力

顺便提一句 你谷用户实属素质极差

动不动问候别人父母是有疾病吗?

祝您NOIP2019 RP--

英文名rainmain 发表于 2019-08-13 20:09:37
你t在哪里sb cin你妈*的m