j为啥要有下限T1[i-1]啊,0不行吗
  • 板块P1717 钓鱼
  • 楼主XSean
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/9 08:47
  • 上次更新2023/11/3 10:58:05
查看原帖
j为啥要有下限T1[i-1]啊,0不行吗
546830
XSean楼主2023/7/9 08:47
#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)

//#define int long long
#define uint unsigned int
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, LL>
#define PLI pair<LL, int>
#define PLL pair<LL, LL>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define Db(x) prf("test(%s): ", x)
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 30, M = 16 * 12 + 10;
int dp[N][M];
int n, h;
int F[N], D[N], T[N], T1[N];
int ans;

int gett(int i, int k){
	return F[i] - (k - 1) * D[i];
}
int get(int i, int k){
	return (F[i] + gett(i, k)) * k / 2;
}

int main(){
	/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	*/
	rd(n, h); h *= 12;
	rep(i, 1, n) rd(F[i]);
	rep(i, 1, n) rd(D[i]);
	rep(i, 1, n-1) rd(T[i]), T1[i] = T1[i - 1] + T[i];
	mms(dp, -1);
	dp[0][0] = 0;
	rep(i, 1, n){
		rep(j, T1[i - 1], h){
			for(int k = 0; k <= j; k++){
				if(dp[i - 1][j - T[i - 1] - k] != -1){
					dp[i][j] = max(dp[i][j], dp[i - 1][j - T[i - 1] - k] + get(i, k));
				}
			} 
			ans = max(ans, dp[i][j]);
		}
	}	
	prf("%d\n", ans);
	return 0;
}





2023/7/9 08:47
加载中...