首页 > 其他分享 >记录大佬的思路

记录大佬的思路

时间:2024-11-07 21:22:09浏览次数:1  
标签:stat 记录 int -- lst ind 思路 大佬 define

洛谷染色问题,即2024CSP-S第三题。
原题复述:
给定一个长度为 n 的正整数数组 A,其中所有数从左至右排成一排。你需要将 A 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分:
设 C 为长度为 n 的整数数组,对于 A 中的每个数 左侧没有与其同色的数,则令 Ci=0。否则,记其左侧与其最靠近的同色数为 Aj ,若 Ai=Aj,则令 Ci=Ai
否则Ci为0。最终得分为 C 中所有整数的和,即你需要最大化最终得分,请求出最终得分的最大值。

一开始考虑肯定是简单的搜索,很可惜,没有重复子问题,所以记忆化搜索用不上。暴搜显然会寄,测试通过前四个点。
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a>b?a:b)
int t,n;int a[200001];int ans[20001];int ind=0;
map<int,int>m;
int s(int ind,int stat)
{
    
    if(ind==n)
    {
        //cout<<bitset<6>(stat)<<endl;
        /*if(m.find(stat)!=m.end())
            return m[stat];*/
        int ans=0;
        for(int i=1;i<n;i++)
        {
            int s=(stat&(1<<i))>>i;//
            int c=0;
            for(int j=i-1;j>=0;j--)
            if((s==((stat&(1<<j))>>j)))
            {
                c=a[i]==a[j]?a[i]:0;
                break;
            }
            //cout<<c<<endl;
            ans+=c;
        }
        //cout<<bitset<9>(stat)<<" "<<ans<<endl;
        //m[stat]=ans;
        return ans;
    }
    int a=s(ind+1,(stat|(1<<ind)));
    int b=s(ind+1,stat);
    int ans=max(a,b);
    return ans;
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
            cin>>a[i];
        ans[ind++]=s(0,0);
    }
    for(int i=0;i<ind;i++)
        cout<<ans[i]<<endl;
    return 0;
}
搜索用不上,下面就要考虑规划,以下是题解大佬的动态规划代码。每次f[i]只会在a[i]已经出现过时产生更新。以s记录相邻的a[i]元素产生的增益。选择lst[a[i]]+1的原因是lst[a[i]]+1可能与lst[a[i]]之前的某点产生增益(之后的增益均被s记录)。
#include <bits/stdc++.h>

#define int long long
#define rint register int
#define endl '\n'
#define m(a) memset(a, 0, sizeof a)

using namespace std;

const int N = 1e6 + 5;

int n, T;
int a[N], lst[N], f[N];
int s[N], ans; 

signed main() 
{
	cin >> T;
	while (T--) 
	{
		cin >> n;
		m(a), m(lst), m(f), m(s);
		for (rint i = 1; i <= n; i++) cin >> a[i];
		for (rint i = 2; i <= n; i++) s[i] = (a[i] == a[i - 1] ? s[i - 1] + a[i] : s[i - 1]);
		for (rint i = 1; i <= n; i++) 
		{
			f[i] = f[i - 1];
			if (lst[a[i]]) f[i] = max(f[i], f[lst[a[i]]+1] + a[i] + s[i] - s[lst[a[i]]+1]);
			lst[a[i]] = i;
		}
		cout << f[n] << endl;
	} 
	return 0;
}

标签:stat,记录,int,--,lst,ind,思路,大佬,define
From: https://www.cnblogs.com/Arc-ux/p/18534016

相关文章

  • 11月7日 NOIP模拟(难题math、矩阵游戏matrix、括号序列seq、道路road) - 模拟赛记录
    PrefaceT1试图找规律失败,正经推反而几分钟就出来了。以后应该少想这些歪门邪道(除非实在闲的蛋疼或者没有一点头绪,且必须要打完所有能打的子任务比如暴力或特殊性质;而且必须在用常规方法思考过后,才能够用一些稍微不那么常规的方法)至于T2、T3、T4,因为知道T1浪费了太多时间,都是......
  • 学习openeuler操作系统的记录本
    1.下载以及配置openeuler在官网里面下载openeuler操作系统,在官网的文档里面里面查看相对应的注意事项,(一定要会阅读官方文档),在官网查看下载的对应操作系统需要的最小cpu,以及磁盘大小等分配合适的虚拟硬盘,配置的过程要一步一步来,防止出现分配不合理,而导致的操作系统无法正常运行的......
  • [考试记录] 2024.11.7 noip模拟赛7
    基础暴力分300pts......
  • 时代峰峻讲课费进口量法撒旦记录卡;个发电量开发建设
    #include<bits/stdc++.h>#defineintlonglong#definefifirst#definesesecond#definepiistd::pair<int,int>#defineebemplace_back#definepbpush_backtypedeflonglongll;typedefunsignedlonglongull;std::mt19937myrand(std::chrono:......
  • VUE模块化开发思路
    构建工具:vite需求:在多个项目下,低层框架可复用,样式可复用,模块可复用。一、项目示例例如当前有两个项目:aaAdmin项目atwtighten项目b项目a和项目b中都有共同的低层逻辑,比如登录,权限验证,前端框架样式等等。在这个两个项目中我们独立出一个公用项目adminCommon,a和b都引用......
  • 【vjudge训练记录】11月个人训练赛2
    训练情况赛后反思A题看错题导致我红温了,C题数组开小又导致我红温了,D题循环太早结束了,导致小数据没答案,我又红温了,F题刚好越界RE了,我又红温了,G题用string会RE,换成char数组就过了。今天全场都在失误红温。。。A题这题是找\(N\timesN\)的字符矩阵中是否包含\(M\timesM\)......
  • 一招解决Mac没有剪切板历史记录的问题
    使用Mac的朋友肯定都为Mac的剪切功能苦恼过,旧内容覆盖新内容,导致如果有内容需要重复输入的话,就需要一次一次的重复复制粘贴,非常麻烦但其实Mac也能够有剪切板历史记录功能,iCopy,让你的Mac也能拥有剪切板历史记录不论是文本、图片、还是文件都可以保存到剪切板上,同时具备分类管......
  • 部分硬件电路设计记录备忘
    1、静电和浪涌保护(TVS/ESD)首先,TVS\钳位二极管\瞬态抑制二极管,可以看做是一种东西,只是称呼不同。然后就是,TVS防护包含两部分:静电释放(ESD)和浪涌(Surge),TVS参数不同,防护侧重也不同。ESD和Surge的主要区别:频率不一样,ESD高频,Surge低频。【1】静电:不用多说了。。。【2】浪涌:......
  • C++ 的前世今生:从“小兄弟”到编程大佬
    当你听到C++这个名字,可能会有点好奇:为什么名字里有个“++”?其实,这个“++”是C++编程中的一个符号,意思是“加一”,也可以理解为“进化版”。C++的名字暗示了它比C语言更加强大、功能更多。那么,这个编程语言是怎么来的?又有什么特别之处呢?让我们用大白话来聊聊C++的历......
  • 【记录】Cordial Sync具身智能协作源码复现及问题解决
    论文简要总结智能体需要合作将家具移动到客厅的指定位置。这个任务与现有的任务不同,它要求智能体在每个时间步都必须进行协调。模型部分1.SYNC-policies(SynchronizeYourActionsCoherently)为了解决智能体在每个时间步都需要协调的问题,研究者提出了SYNC-policies。这......