JZTXT

《看了受制了》第三十二天，10道题，合计174道题

发布时间 2023-10-01 20:25:36作者: wxzcch

2023年10月1日
今天是DP!加油吧哎，接受自己的菜，也得接受之前造成的影响可恶啊。

Awcing282 石子合并

题目大意

把相邻的石子，进行合并，花费是两堆石子的数量和。问把所有石子合并成一堆的最小花费。

题目理解

  • yxcDP分析大法
  • 是经典的区间 DP
  • 因为只能合并相邻的便是Dp问题
  • 我们把f[i][j]看作合并从[i, j]为一堆的集合
  • 属性便是个数
    切记！区间DP的枚举方式。

代码实现

/* 
y式dp分析法：化0为整的过程

状态表示：
集合：所有将 [i, j] 合并成一堆的方案的集合
属性：每一个方案的最小值

状态转化：
因为：f[i][j] 代表把从[i, j] 合并成一堆的方案集合那么

f[i][j] = min(f[i][j], f[i - 1][k] + f[k + 1][j])

k 是从 i 一直到 j - 1
*/
const int N = 310;
int w[N];
int d[N][N];

void solve()
{
	int n;
	cin >> n;

	for(int i = 1; i <= n; i++)cin >> w[i], w[i] += w[i - 1];

	// 一般都是枚举区间长度
	for(int len = 2; len <= n; len++)
		for(int i = 1; i + len - 1 <= n; i++)	// 枚举左端点
		{
			// 枚举右端点
			int j = i + len - 1;
			d[i][j] = INF;
			for(int k = i; k <= j - 1; k++)
				d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j] + w[j] - w[i - 1]);
		}


	cout << d[1][n];
	return;
}

Acwing900 整数划分

题目理解

一步步分析出来了！

/*
f[i][j] 表示，用前i个数，组合成j的方法数

状态表示：
集合：     1 ~ i 能组合成数字j的集合
属性：     cnt方案数

状态转移：

f[i][j] = f[i - 1][j] + ()

f[i - 1][j] 是1 ~ i减一组合成`j`的方法

如果我选了j这个数，f[i][j]
i是可以选择 [0, j / i]个
f[i][j] = sum(f[i - 1][j], f[i - 1][j - 1 * i], f[i - 1][j - 2 * i], ... f[i - 1][j - k * i])

f[i][j - i] = sum(f[i - 1][j - i], f[i - 1][j - 2 * i], f[i - 1][j - 3 * i], ...)

f[i][j] = f[i - 1][j] + f[i][j - i];

最后的答案就是f[n][n]
*/

代码实现

const int N = 1010;
int d[N][N];
void solve()
{
    int n;
    cin >> n;

    for(int i = 0; i <= n; i++) d[i][0] = 1;

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n; j++)
        {
            d[i][j] = d[i - 1][j];

            if(j >= i)
                d[i][j] = (d[i - 1][j] + d[i][j - i]) % Mod;
        }

    cout << d[n][n];
    return;
}

Acwing5268 Python缩进

题目理解

/*
ysdp分析法

f[i][j] 表示第i条语句缩进了j级组成的方案数

如果前面一句是f: f[i][j] = f[i - 1][j - 1]
如果前面一句是S:
f[i][j] = f[i - 1][j] + f[i][0] + f[i][1] + ... f[i][j - 1];
f[i][j + 1] = f[i][0] + ... + f[i][j] 

*/

代码实现

const int N = 5e3 + 10;

int d[N][N], w[N];
string c[N];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> c[i];

    d[1][0] = 1;

    for(int i = 2; i <= n; i++)
        for(int j = i - 1; j >= 0; j--)
        {
            if(c[i - 1] == "f")
            {
                if(j) d[i][j] = d[i - 1][j - 1];    //如果没法缩进就是0喽
            }

            else{
                d[i][j] = (d[i - 1][j] + d[i][j + 1]) % Mod;
            }
        }

    int res = 0;
    for(int i = 0; i < n; i++)
        res = (res + d[n][i]) % Mod;
    cout << res;
    return;
}

Atcoder ABC322 E Prodect Development

题目理解

仔细读题后发现是个k维背包的问题，难点在于我们如何表示状态！！我们采用状态压缩表示

  • 我们将k维的压缩到1维，如何表示？就是将其转化为p + 1进制的数
  • 这样我们就可以用一个特殊进制下的数，实现了k维状态表示。
  • 那么我们只需要写好状态即可。
/* 如果在体积为 j 的情况下且选择了第i个方案，的 p + 1进制表示为 g
那么我们可以得到：
f[i + 1][g] = min(f[i + 1][g], f[i - 1][j] + c[i])
如果我们没选:
f[i + 1][g] = min(f[i + 1][j], f[i][j])

代码实现

ll d[M][N], c[M], a[M][10];
ll n, k, p;

ll getid(vector<ll> v)    // 得到p进制
{
	ll res = 0;
	for(ll i = 0; i < k; i++)
		res = res * (p + 1) + v[i];
	return res;
}

vector<ll> getv(ll u)    // p进制转化成 k维
{
	vector<ll> res;
	for(ll i = 0; i < k; i++)
	{
		res.push_back(u % (p + 1));
		u /= (p + 1);
	}
	reverse(res.begin(), res.end());
	return res;
}

void solve()
{
	cin >> n >> k >> p;

	for(int i = 0; i < n; i++)
	{
		cin >> c[i];
		for(int j = 0; j < k; j++)
			cin >> a[i][j];
	}

	memset(d, LINF, sizeof d);
	d[0][0] = 0;

	for(int i = 0; i < n; i++)
		for(int j = 0; j < N; j++)
		{
			if(d[i][j] < LINF)
			{
				d[i + 1][j] = min(d[i + 1][j], d[i][j]);
				auto v = getv(j);	//得到当前这个体积下对应的向量

				// 更新这个向量, 得到如果选择了这个值会加到什么样子
				for(int l = 0; l < k; l++)
					v[l] = min(p, v[l] + a[i][l]);

				ll g = getid(v);	// 获取向量下对应的状态,转成p + 1状态下的数

				d[i + 1][g] = min(d[i + 1][g], d[i][j] + c[i]);
			}
		}

	vector<ll> res(k, p);
	ll j = getid(res);	// 得到答案应该是哪个状态

	if(d[n][j] == LINF) cout << -1 << endl;
	else cout << d[n][j] << endl;
	return;
}

Div.4 Round871 A LoveStory

题目大意

问，一个长度为\(10\)的字符串，里面有几个和codeforces不一样。

题目理解

直接遍历即可

代码实现

void solve()
{
	string tmp = "codeforces";
	string s;
	cin >> s;
	int cnt = 0;

	for(int i = 0; i < 10; i++) 
		if(s[i] != tmp[i])
			cnt++;

	cout << cnt << endl;
	return;
}

Div.4 Round871 B Blank Space

题目大意

最长的0串有多长

题目理解

遍历一次，遇到1更新答案，遇到0就cnt++

代码实现

void solve()
{
	int res = 0, cnt = 0;

	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int b;
		cin >> b;
		if(b == 1)
		{
			res = max(res, cnt);
			cnt = 0;
		}else cnt++;
	}

	res = max(cnt, res);
	cout << res << endl;
	return;
}

Div.4 Round871 C Mr. Perfectly Fine

题目大意

有n本书，每本书可以带来一个效果，01,10,11,00,0代表可以学会技能，1代表可以学会第二个技能。问我们学会技能的最小花费是多少。

题目理解

学会技能有两种途径：

  • 一本书学会
  • 两本数学会

所以存一下三种情况的最小值，然后输出两本书的和及一本书学会两者间小的。

代码实现

void solve()
{

	int n;
	cin >> n;
	int time1 = INF, time2 = INF, time3 = INF;
	for(int i = 1; i <= n; i++)
	{
		int b, c;
		cin >> b >> c;

		if(c == 0) continue;

		if(c == 10)
			time1 = min(time1, b);
		else if(c == 1)
			time2 = min(time2, b);
		else if(c == 11)
			time3 = min(time3, b);
	}

	if(time3 == INF && (time1 == INF || time2 == INF))
		cout << -1 << endl;
	else{
		cout << min(time3, time1 + time2) << endl;
	}

	return;
}

Div.4 Round871 D Glod Rush

题目大意

给出两个数n和m，看能不能把n通过只分成\(2 / 3 * n 和 1 / 3 * n\)的方式得到m

题目理解

用个vector，存一下，只要是3的倍数都可以分，就只分三的倍数，分完的就标为-1即可。看过程中有没有出现m

代码实现

bool check(vector<int> a)
{
	for(int i = 0; i < a.size(); i++)
		if(a[i] % 3 == 0)
			return true;

	return false;
}

void solve()
{

	int n, m;
	cin >> n >> m;
	if(m > n)
		cout << "NO" << endl;
	else if(m == n)
		cout << "YES" << endl;
	else{
		vector<int> a;
		a.push_back(n);

		while(check(a))
		{
			for(int i = 0; i < a.size(); i++)
			{
				if(a[i] == m)
				{
					cout << "YES" << endl;
					return;
				}else{
					if(a[i] % 3 == 0)
					{
						int t1 = a[i] / 3, t2 = a[i] / 3 * 2;
						if(t1 == m || t2 == m)
						{
							cout << "YES" << endl;
							return;
						}
						if(t1 % 3 == 0)
							a.push_back(t1);
						if(t2 % 3 == 0)
							a.push_back(t2);
						a[i] = 1;		
					}
				}
			}
		}

		cout << "NO" << endl;
	}

	return;
}

Div.4 Round871 E The Lakes

题目大意

问连通数字的，最大和是多少？

题目理解

BFS板子题，敲一遍即可

代码实现

const int N = 1010;
int n, m;
int g[N][N];
bool st[N][N];
int res = 0;

void bfs(int t1,int t2)
{

	int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};

	queue<pair<int, int>> q;
	q.push({t1, t2});
	int d = g[t1][t2];
	while(q.size())
	{
		auto t = q.front();
		q.pop();

		st[t.x][t.y] = true;

		for(int i = 0; i < 4; i++)
		{
			int a = t.x + dx[i], b = t.y + dy[i];
			if(a >= 1 && a <= n && b >= 1 && b <= m && !st[a][b] && g[a][b] != 0)
			{
				d += g[a][b];
				q.push({a, b});
				st[a][b] = true;
			}
		}
	}

	res = max(res, d);
}


void solve()
{
	memset(g, 0, sizeof g);
	memset(st, 0, sizeof st);
	res = 0;

	cin >> n >> m;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> g[i][j];

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(!st[i][j] && g[i][j] != 0)
				bfs(i, j);

	cout << res << endl;
	return;
}

Div.4 Round871 F Forever Winter

题目大意

问中心的点的度是多少，以及以它相连的点的度是多少。

题目理解

  • 稠密图，用邻接矩阵存一下，有边的标记为1
  • 如果只有两种度，那么x必为0
  • 我们找到一个度为1的点，然后遍历和它连结的点的度，找到一个度不为1的点就是x
  • 然后我们在找跟x连结的点且度不为1的即可，就是y

代码实现

const int N = 210;
int k[N], g[N][N];

void solve()
{
	memset(g, INF, sizeof g);
	memset(k, INF, sizeof k);
	int n, m, u, v;
	scanf("%d%d", &n, &m);

	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d", &u, &v);
		g[u][v] = g[v][u] = 1;
		if(k[u] != INF && k[u] != 0) k[u]++;
		if(k[v] != INF && k[v] != 0) k[v]++;
		if(k[u] == INF) k[u] = 1;
		if(k[v] == INF) k[v] = 1;
	}

	vector<int> a;
	for(int i = 1; i <= n; i++)
		if(k[i] != INF)
			a.push_back(i);

	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());

	if(a.size() == 2)
	{
		cout << a[1] << 0 << endl;
	}else{


		int flag;
		for(int i = 1; i <= n; i++)
			if(k[i] == 1)
			{
				flag = i;
				break;
			}
		int x;
		for(int i = 1; i <= n; i++)
			if(g[flag][i] == 1 && k[i] != 1 && k[i] != INF)
			{
				x = k[i];
				flag = i;
				break;
				
			}
		int y;
		for(int i = 1; i <= n; i++)
			if(g[flag][i] == 1 && k[i] != 1 && k[i] != INF)
			{
				y = k[i];
				break;
			}
		cout << y << " " << x - 1<< endl;
	}


	return;
}