[数据结构与算法]周末总结——（并查集+dp）

这一周学的就比较杂了，刚开始还在做dp的题，后来想还是做点别的，然后又在做并查集的题，到了周末，遇到了一个并查集的题涉及了图论的其他知识，然后又开始看图论的基础知识。
然后就是又打了一次div2，发现要不就是看不懂题，要不就是没涉及到算法的，出了3个第四个没翻译出来。等翻译完在出题解。
就简单地写几个我认为这周比较有意义的题解吧：

P1455 搭配购买

链接：
https://www.luogu.com.cn/problem/P1455

题意：
就是给你一定的钱，让你买东西，求你买的东西的价值最大，前提就是有的物品，你买了之后还需要连带着买别的。

刚读完题我就在扣这个题，越想越复杂。然后我忽然之间，就把题分开看了看，这不就是一个背包。。。。然后就没有然后了。

思路：

首先根据并查集，把能够相关联的关联起来。在用数组来存起来他们关联之后的价值和，还有物价和。
最后再根据0/1背包来求出最大价值。

代码：

#include<bits/stdc++.h>
using namespace std;
int father[10001];//并查集数组

int find(int x)//并查集函数
{if(father[x]==x)return x;
	return father[x]=find(father[x]);}

int c[10001],d[10001],f[10001];//DP数组

int main()
{
	int n,m,w;
cin>>n>>m>>w;
	for(int i=1;i<=n;i++)//初始化并查集
	father[i]=i;
	for(int i=1;i<=n;i++)
	cin>>c[i]>>d[i];
	int x,y;
	for(int i=1;i<=m;i++)//并查集
	{
		cin>>x>>y;
		father[find(x)]=find(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(father[i]!=i)
		{
			d[find(i)]+=d[i];
			d[i]=0;
			c[find(i)]+=c[i];
			c[i]=0;
		}
	}

	for(int i=1;i<=n;i++)//DP
	{
	    for(int v=w;v>=c[i];v--)
	    {
	    	f[v]=max(f[v],f[v-c[i]]+d[i]);
		}
	}
	cout<<f[w];
	return 0;
}

其实并查集并不是很难，在做提高-的时候感觉他和其他的算法相比，还是比较容易做的。但是他和其他的算法一起出现就比较麻烦了。

P1070 [NOIP2009 普及组] 道路游戏

链接：
https://www.luogu.com.cn/problem/P1070

题意：

一个环形马路，环形马路上有几个机器厂，每一个而机器厂都可以制造机器人，他们制造的机器人可以去扫马路，每扫一个马路都会给你钱（当然买机器也会消耗钱），扫马路的钱会根据时间的改变而改变，每一次只能派出一个机器人，一个机器人结束必须立刻派出并一个机器人，最后让你来求出你能够获的钱的最大值。

这个题是目前为止第一个省-的题，确实有难度。主要的是需要关注的变量有点多，既要关注时间，有要关注扫地的钱。

思路：

这个题首先想的是怎么成环，因为之前的成环都是在数据之后又加上一组相同的数据，这样来成环，但是这样形成的环数据就变得有点多，不适合这个题，然后又看了看别人的代码发现了，并外一种代码成环的代码感觉还是比较巧妙的。arr[i%n]到n之后又跳转到0，这样好像就会节省点空间吧。
继续回到这个题上来，因为是dp，所以最重要的就是dp方程了，dp[i]代表的是前i时间的最大值。（其实用dp[i][j][k]更加的直观，dp代表i时间内，j工厂的机器人，走到k个地方时候的最大值）在通过枚举时间，枚举点，枚举走的步数构造方程。直接上代码吧。

代码：

#include <bits/stdc++.h>
#include<iostream>
#include <iostream>
using namespace std;
 int read(){int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;}

int mp[1005][1005],n,m,p,cost[1005],dp[1005],ans,t;
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j]=read();//第i条边，j时刻
        }
    }
    for(int i=1;i<=n;++i){//每个点的花费
    cost[i]=read();
    }
    for(int i=1;i<=m;++i){//初始化
        dp[i] = -1e9;//由于有可能有负数解
    }
    for(int i=1;i<=m;++i){//枚举时间
        for(int j=1;j<=n;++j){//枚举点
            ans = -cost[j]+dp[i-1];
            for(int k=0;k<p&&i+k<=m;++k){//枚举走的步数
                t = j+k > n ? ((j+k)%n) : j+k;//处理环
                ans += mp[t][i+k];
                dp[i+k] =/*dp[i+k] > ans ? dp[i+k] : ans;*/ max(dp[i+k],ans); //更新
            }
        }
    }
    cout<<dp[m];
    return 0;

}

说实话做这种题还是有点困难的。这两个题就是这周感觉比较有意义的题吧，这周还是蛮兴奋的，cf终于突破1200了，但是昨天问了问一个其他学校的队员，他们平均就1400—1500，瞬间感觉，我们还是太菜了吧，只能说况且他们大二的还有那种分2000以上的。其实别的也没啥说的，就是感觉自己还是不够努力吧，和别人还是会有明显的差距，继续吧！