这题目给了三种做法，两种是动态规划做法，一种是贪心加枚举，还有一种是堆写法，这可以促进我对动态规划的理解，所以在此贴出四种板子，并且给出解释
第一种做法，自下二上更新
第二种做法，自上而下更新
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int a[N], b[N], c[N], presum[N];
int t, f[2][1010];
int main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
#else
ios::sync_with_stdio(0);
#endif
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
for (int i = 2; i <= n; ++i) {
cin >> c[i];
presum[i] = c[i] + presum[i - 1];
}
cin >> t;
n = lower_bound(presum + 1, presum + 1 + n, t) - presum - 1;
int ans = 0;
for (int i = 1; i <= n; ++i) {
memset(f[i & 1], 0, sizeof f[0]);
for (int j = presum[i] + 1; j <= t; j++) {
f[i & 1][j] = f[(i - 1) & 1][j - c[i]];
int sum = a[i];
for (int k = 1; k <= min((a[i] + b[i] - 1) / b[i], j - presum[i]); k++) {
f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - k - c[i]] + sum);
sum += a[i] - k * b[i];
}
ans = max(ans, f[i & 1][j]);
}
}
cout << ans;
}
点击查看代码
//多路归并：如何归并
//T - l[i]:余下可以调度时间
//for i 1 -n
// T = T - li;
// res = work(i,T);
//work(n,T)
//在序列第一层 比较大小 选出最大
//for j 1 - n
// if(get(j) > get(t))
// t = j;
// res += get(j);//选出最大 n次后返回
// spend[t]++;//在这里钓鱼分钟++
//结果看着好像是一个鱼塘一直掉了spend[i]分钟
//其实是n次判断结果
//1-i 剩余时间不同 多路归并m次选择 n次比较出最大++ o(n * m * n)
///if(get(j)>get(t)) t = j选出n个里面最大 spend[t]++;//在该处时间++
//get(k): a[k] - d[k] * spend[k];
//
//过程像来回 实际是帮我们选择每个鱼塘应该待多少时间
//
#include<bits/stdc++.h>
#define N 110
using namespace std;
int spend[N],a[N],d[N],x[N];
int get(int k)
{
//开始鱼塘k钓鱼数 - 鱼塘k每分钟减少数 * k鱼塘掉了多少分钟
return max(0,a[k] - d[k] * spend[k]);
}
int work(int n,int T)
{
memset(spend,0,sizeof spend);
int res = 0;//i T - x[i] 钓鱼数
for(int i = 0;i<T;i++) //T次选择
{
int t = 1;//默认从一个开始钓
for(int j =1;j<=n;j++)//找出该次最大
{
if(get(j) > get(t))
t = j;
}
res += get(t);//当前行最大钓鱼数
spend[t]++;//选择t序列钓鱼时间++
}
return res;
}
int main()
{
int n,m,T;
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;i++) scanf("%d",&d[i]);
for(int i = 2;i<=n;i++)
{
scanf("%d",&x[i]);
x[i] += x[i-1];
}
// for(int i = 1;i<=n;i++)
// {
// printf("a[%d]:%d\nd[%d]:%d\nx[%d]:%d\n",i,a[i],i,d[i],i,x[i]);
// }
scanf("%d",&T);
int res = 0;
for(int i = 1;i<=n;i++)
{
res = max(res,work(i,T-x[i]));
}
cout<<res<<"\n";
}
点击查看代码
//多路归并：如何归并
//T - l[i]:余下可以调度时间
//for i 1 -n
// T = T - li;
// res = work(i,T);
//work(n,T)
//在序列第一层 比较大小 选出最大
//for j 1 - n
// if(get(j) > get(t))
// t = j;
// res += get(j);//选出最大 n次后返回
// spend[t]++;//在这里钓鱼分钟++
//结果看着好像是一个鱼塘一直掉了spend[i]分钟
//其实是n次判断结果
//1-i 剩余时间不同 多路归并m次选择 n次比较出最大++ o(n * m * n)
///if(get(j)>get(t)) t = j选出n个里面最大 spend[t]++;//在该处时间++
//get(k): a[k] - d[k] * spend[k];
//
//过程像来回 实际是帮我们选择每个鱼塘应该待多少时间
//
#include<bits/stdc++.h>
#define N 110
using namespace std;
int spend[N],a[N],d[N],x[N];
int get(int k)
{
//开始鱼塘k钓鱼数 - 鱼塘k每分钟减少数 * k鱼塘掉了多少分钟
return max(0,a[k] - d[k] * spend[k]);
}
int work(int n,int T)
{
memset(spend,0,sizeof spend);
int res = 0;//i T - x[i] 钓鱼数
for(int i = 0;i<T;i++) //T次选择
{
int t = 1;//默认从一个开始钓
for(int j =1;j<=n;j++)//找出该次最大
{
if(get(j) > get(t))
t = j;
}
res += get(t);//当前行最大钓鱼数
spend[t]++;//选择t序列钓鱼时间++
}
return res;
}
int main()
{
int n,m,T;
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;i++) scanf("%d",&d[i]);
for(int i = 2;i<=n;i++)
{
scanf("%d",&x[i]);
x[i] += x[i-1];
}
// for(int i = 1;i<=n;i++)
// {
// printf("a[%d]:%d\nd[%d]:%d\nx[%d]:%d\n",i,a[i],i,d[i],i,x[i]);
// }
scanf("%d",&T);
int res = 0;
for(int i = 1;i<=n;i++)
{
res = max(res,work(i,T-x[i]));
}
cout<<res<<"\n";
}