钓鱼

第一行一个整数n，表示湖的个数

第二行一个整数H，表示佳佳的空闲时间

第三行有n个整数，依次表示每个湖第一个5分钟能钓到鱼的数量

第四行有n个整数，依次表示以后的每5分钟钓鱼数量比前一个5分钟钓鱼数量减少的数量

第五行有n-1个整数， $T_i$ 表示由第i个湖到第i+1个湖需要花 $5 \times T_i$ 分钟的路程

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 732K, 提交时间: 2020-05-03 09:12:01

#include<bits/stdc++.h>
using namespace std;
int n,x,a[999],b[999],c[999],d[2222][2222]={0},m=0,s,i,j,v,y,l;
int main(){cin>>n>>x;x*=12;
    for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=n;i++)cin>>b[i];
    for(i=1;i<n;i++)cin>>l,c[i+1]=c[i]+l;
    for(i=1;i<=n;i++){
        for(j=1;j<=x-c[i];j++){d[i][j]=d[i][j-1];
            for(v=0;v<=j;v++){
                if((v-1)*b[i]<a[i]){s=0;
				    for(y=0;y<v;y++)s+=a[i]-(b[i]*y);
                    d[i][j]=max(d[i][j],d[i-1][j-v]+s);
                }
            }m=max(m,d[i][j]);
        }
    }cout<<m;
}

C++ 解法, 执行用时: 306ms, 内存消耗: 2028K, 提交时间: 2021-07-24 20:30:44

#include<bits/stdc++.h>
#define N 105
using namespace std;

int n,H,ans,w[N],c[N],t[N],f[N*10][N][N];

void dfs(int T,int l,int lt,int F)
{
    if(T<0||l>n||f[T][l][lt]>F) return;
    f[T][l][lt]=F,ans=max(ans,F);
    dfs(T-1,l,lt+1,F+w[l]-c[l]*lt);
    dfs(T-t[l+1],l+1,0,F);
}

int main()
{
    scanf("%d%d",&n,&H);
    for(int i=1;i<=n;i++)   scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)   scanf("%d",&c[i]);
    for(int i=2;i<=n;i++)   scanf("%d",&t[i]);
    dfs(H*12,1,0,0);
    printf("%d",ans);
    return 0;
}

详情