首页 > 其他分享 >C. Tenzing and Balls

C. Tenzing and Balls

时间:2024-05-31 14:33:54浏览次数:16  
标签:Balls Tenzing ll cin 消掉 mp include dp

链接:https://codeforces.com/problemset/problem/1842/C or https://www.luogu.com.cn/problem/CF1842C

大概的思路就是利用dp[i]记录前i个数据最多消掉的数字个数,然后对∀j:a[i] == a[j] && j < i进行dp[i] = dp[j-1] + i-j+1的递推
优化:

代码:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;

const int N = 2e5 + 10;
ll dp[N],a[N],mp[N];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	ll t; cin >> t;
	while (t--)
	{
		ll n; cin >> n;
		memset(dp, 0, sizeof(dp));
		memset(mp, -0x3f3f3f3f, sizeof(mp));//这个初始设置成最小
		for (ll i = 1; i <= n; i++)
		{
			ll x; cin >> x;
			a[i] = x;
		}
		dp[1] = 0;//dp:消掉的数量
		for (ll i = 1; i <= n; i++)
		{
			//dp[i] =  max(dp[j - 1] + i - j + 1,dp[i]);
			dp[i] = max(dp[i - 1], mp[a[i]] + i);
			mp[a[i]] = max(mp[a[i]], dp[i - 1] - i + 1);
		}
		cout << dp[n]<<'\n';

	}
	return 0;
}

标签:Balls,Tenzing,ll,cin,消掉,mp,include,dp
From: https://www.cnblogs.com/zzzsacmblog/p/18224540

相关文章

  • C - Merge the balls
    C-Mergetheballshttps://atcoder.jp/contests/abc351/tasks/abc351_c 思路使用stack记录序列路径对栈顶两个元素尝试做缩减处理。 Codehttps://atcoder.jp/contests/abc351/submissions/52873456intn;stack<longlong>sq;intmain(){cin>>n;......
  • Colored Balls
    这道题目的模型倒是可以记住我们发现这个配对很像摩尔投票,所以考虑原数列是否有主元素对于一个集合,我们选出其中最大的\(a_i\),假设剩余的\(a\)的和小于等于\(a_i\)(此时有主元素),那么比较显而易见的就是最终会分出\(a_i\)个组;否则的话,我们考虑下界\(\lceil\frac{\suma}{2}\rcei......
  • CF1842H Tenzing and Random Real Numbers 题解
    题目链接点击打开链接题目解法实数的概率好反直觉!对\(1\)做限制不是很好做,考虑变成正负性的限制(即对\(0\)做限制)令\(y_i=x_i-0.5\),那么限制就变成了\(y_i+y_j\le0,\;y_i+y_j\ge0\)这里要给出一些实数概率的结论:实数下,\(x=y\)的概率为\(0\),因为\(\frac{1}{\inft......
  • CodeForces 1951G Clacking Balls
    洛谷传送门CF传送门考虑用相邻两个球之间的距离来描述一个状态。设距离序列为\(a_1,a_2,\ldots,a_k\)(忽略\(0\))。考虑鞅与停时定理,设一个状态的势能为\(\sum\limits_{i=1}^kf(a_i)\),一次操作能使得势能期望减少\(1\)。那么:\[1=\frac{1}{n}\sum\limits_{i=1}^k......
  • D. Colored Balls
    D.ColoredBallsThereareballsof$n$differentcolors;thenumberofballsofthe$i$-thcoloris$a_i$.Theballscanbecombinedintogroups.Eachgroupshouldcontainatmost$2$balls,andnomorethan$1$ballofeachcolor.Considerall$2^n$set......
  • 14 CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)C. Tenzing and Balls(dp+前缀
    思路:dp还是挺明显的,思路可以参考最长上升子序列有点dp的感觉\(f[i]\)表示考虑前\(i\)个数,的最大值当前数有两种删或不删不删:\(f[i]=f[i-1]\);删:\(f[i]=max{f[j-1]+i-j+1}\)这个转移是\(O(n^2)\)的显然时间上来不及考虑优化,第一层循环一定是省不了的考虑优化掉第二层循环......
  • [AGC037B] RGB Balls
    题意有\(n\)个人,\(3\timesn\)个球,球有三种颜色,每种颜色恰好\(n\)个。给每个人每种颜色的球各一个,按照在原序列的顺序分别设为\(p1,p2,p3\)。试求使得\(\sump_3-p_1\)最小的方案数。Sol其实直接考虑就行了,没必要想那么复杂。假设当前的球的颜色为\(R\),之前......
  • 小球游戏 -- balls in a line
    ;Ballsinaline;withA-Starpanthfind;2023.6EnableExplicit#wd=65;width#Xc=20#Yc=20#obstruct=1#channel=0#BallsCount=10DeclareModuleLinearlySpacedValueDeclare.fFloat(IncrementID.l,IncrementMax.l,MinValue.f,MaxValue.f)EndDe......
  • ABC332G Not Too Many Balls 题解
    第\(i\)种球有\(a_i\)个,共\(n\)种。第\(i\)种箱子最多共装\(b_i\)个球。共\(m\)种。第\(i\)种球在第\(j\)种箱子里至多放\(ij\)个。问所有箱子放的球数最多是多少。\(1\leqn\leq500,1\leqm\leq5e5,0\leqa_i,b_i\leq1e12\)。很容易建出网络流模型。......
  • CF1842E Tenzing and Triangle 题解
    题意不多赘述。思路如果两个所选的三角形有重合部分的话,那么这种情况肯定是不会出现的。因为如果把这两个三角形合成一个大三角形的话,不仅覆盖面积会增大,而且花费的代价还不会多。于是我们可以想到用dp来解决,设\(dp_{i}\)表示删完横坐标为\(0\)到\(i\)中的点的最小代价......