首页 > 其他分享 >P2198 题解

P2198 题解

时间:2023-10-18 22:34:58浏览次数:40  
标签:__ ch read 题解 times le P2198 int128

解题思路

激光塔一定在最后。\(f_{i,j}\) 表示前 \(i\) 个位置放 \(j\)(\(j\le i\))个放射塔,那么 \(i-j\) 个干扰塔的伤害。

若第 \(i\) 个位置放放射塔:\(f_{i,j}=f_{i-1,j-1}+(j-1)\times g\times[t+b\times(i-j)]\)
若第 \(i\) 个位置放干扰塔,也就是 \(j<i\):\(f_{i,j}=\max\{f_{i-1,j-1}+(j-1)\times g\times[t+b\times(i-j)],f_{i-1,j}+j\times g\times[t+b\times(i-j-1)]\}\)。

最终答案为 \(\max\limits_{0\le j\le i\le n}\{f_{i,j}+(n-i)\times(r+j\times g)\times[t+b\times(i-j)]\}\)。

由于答案过大,所以建议开 __int128_t 或者高精度。

代码

#include<bits/stdc++.h>
using namespace std;
__int128_t n, r, g, b, t, ans, f[1030][1030];
inline __int128_t read() {
  __int128_t x = 0;
  bool flag = 0;
  char ch = getchar();
  while(ch < '0' || ch > '9') {
    if(ch == '-') {
      flag = 1;
    }
    ch = getchar();
  }
  while(ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  if(!flag) {
    return x;
  } else {
    return -x;
  }
}
inline void write(__int128_t x) {
  if(x < 0) {
    x = -x;
    putchar('-');
  }
  if(x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
int main() {
	n = read(), r = read(),  g = read(), b = read(), t = read();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= i; j++) {
			f[i][j] = f[i - 1][j - 1] + (j - 1) * g * (t + b * (i - j));
			if(i != j) {
				f[i][j] = max(f[i][j], f[i - 1][j] + j * g * (t + b * (i - j - 1)));
			}
		}
	}
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= i; j++) {
			ans = max(ans, f[i][j] + (n - i) * (r + j * g) * (t + b * (i - j)));
		}
	}
	write(ans);
	return 0;
}

标签:__,ch,read,题解,times,le,P2198,int128
From: https://www.cnblogs.com/cyf1208/p/17773533.html

相关文章

  • P7974 题解
    解题思路首先可以确保每一次列的方向一定不会与\(s\)到\(t\)的方向相反。不妨设\(l=\min\{s,t\}\),\(r=\max\{s,t\}\)。对于每次移动,所花体力值如下:显然,从\(l\)到\(r\),一定要翻过\([l,r]\)间最高的一个,区间最大我们毫不犹豫地选择ST表,然后我们思考一下,令\(h_x=\m......
  • P4814 题解
    解题思路对于每条边\((u,v)\),权值为\(w\),假设存在一条经过这一条边的路径,其最短距离为\(a\)到\(u\)的最短路加上\(v\)到\(b\)的最短距离加上\(w\),若这个值都大于\(d\),则不可能关闭这条边。由于边权非负,所以可采用dijkstra来处理最短路。因为为有向边,所以可以再建......
  • C++常见入门题题解
    前言因为本人目前比较菜,所以给出的题解都是按照自己的学习进度来的,所以难度是一个循序渐进的过程,由于本人水平有限,望读者能够指出谬误,共同进步。回文数输出#include<bits/stdc++.h>//万能头usingnamespacestd;intmain(void){vector<int>font;//定义一个整型的向......
  • 题解 CF1651F【Tower Defense】
    题解CF1651F【TowerDefense】problem一个塔防游戏。一共有\(n\)个塔按\(1\simn\)的顺序排成一列,每座塔都有魔力容量\(c_i\)和魔力恢复速率\(r_i\)。对于一座塔\(i\),每过一秒它的魔力\(m_i\)会变为\(\min(m_i+r_i,c_i)\)。每座塔初始时满魔力。一共有\(q\)个......
  • 【题解 CF840C & P4448】 On the Bench & 球球的排列
    OntheBench题面翻译给定一个序列\(a(a_i\le10^9)\),长度为\(n(n\le300)\)。试求有多少\(1\)到\(n\)的排列\(p_i\),满足对于任意的\(2\lei\len\)有\(a_{p_{i-1}}\timesa_{p_i}\)不为完全平方数,答案对\(10^9+7\)取模。题目描述Ayearagoonthebenchinpu......
  • P9506 题解
    blog。Firstsolution/kx。容易想到断环成链。打开标签发现是DP,于是就可以DP了。code,时间复杂度\(O(\text{能过})\)。......
  • 算法笔记-有效括号序列题解
    描述给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列。括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。数据范围:字符串长度0≤n≤10000要求:空间复杂度O(n),时间复杂......
  • NOIP2018PJ T3 摆渡车(2023.10第二版题解)
    题目链接 题意:时间轴上分布着$n$位乘客($1\len\le500$),$i$号乘客的位置为$t_i$(0\let_i\le4\times10^6),用互相距离不小于$m$的车次将时间轴分为若干部分,并管辖以自己为右端点的这个区间(除了第一趟车包括$0$,其他车次左开右闭),求最小费用和。每个车次的费用来自:管辖区间内所......
  • AT_arc100_b 题解
    题意这道题是让我们把一段区间分成四个不为空的连续子序列,并算出每个区间的和,最后用四个和的最大值减去最小值,算出最终答案。分析大家首先想到的肯定是暴力法用三个循环枚举四个区间,对于每一个区间,在单独算和,这样的时间复杂度$O(n^4)$,肯定会超时。现在我们进行优化:最后求和的......
  • P4899 [IOI2018] werewolf 狼人 题解
    P4899[IOI2018]werewolf狼人题解题目描述省流:\(n\)个点,\(m\)条边,\(q\)次询问,对于每一次询问,给定一个起点\(S\)和终点\(T\),能否找到一条路径,前半程不能走\(0\thicksimL-1\)这些点,后半程不能走\(R+1\thicksimN-1\)这些点。中途必须有一个点在\(L\thicksimR\)之......