NOWCODER_10_9

A

原题链接

超简单的题，但是数有可能是负数啊啊啊啊啊啊啊啊啊啊啊啊啊啊！

#include <iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N];
signed main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	//可能是负数
    int ans =(a[1] + a[2]) * a[n];
    ans = min(ans, (a[n] + a[n - 1]) * a[1]);
    for(int i = 1; i + 2 <= n; i++)
    {
        ans = min(ans, (a[i] + a[i + 1]) * a[i + 2]);
        ans = min(ans, (a[i] + a[i + 2]) * a[i + 1]);
        ans = min(ans, (a[i + 1] + a[i + 2]) * a[i]);
    }
    cout << ans;
	return 0;
}

B

原题链接

按照题目分类即可

#include <iostream>
#include <map>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
#define int long long
deque<char> v;
int a[15];
map<string, int> m = { {"QQ",1},{"QW",2},{"QE",3},{"WQ",4},{"WW",5},{"WE",6},{"EQ",7},{"EW",8},{"EE",9},{"R",10} };
string s;
int ans = 0;
signed main()
{
	for (int i = 1; i <= 10; i++) cin >> a[i];
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		if (v.empty())
		{
			if (s[i] == 'R') ans += a[m["R"]];
			else v.push_back(s[i]);
		}
		else
		{
			char t = v.front();
			v.pop_front();
			if (s[i] == 'R') continue;
			else
			{
				string que = "";
				que += t;
				que += s[i];
				ans += a[m[que]];
			}
		}
		
	}
	cout << ans;
	return 0;
}

C

原题链接

多重背包问题

#include <iostream>
using namespace std;
#define int long long
int v[15], num[5];
const int N = 150;
int dp[N][N][N];
signed main()
{
    for(int i = 1; i <= 10; i++) cin >> v[i];
    for(int i = 1; i <= 4; i++) cin >> num[i];
    for(int Q = 0; Q <= num[1]; Q++)
    {
        for(int W = 0; W <= num[2]; W++)
        {
            for(int E = 0; E <= num[3];E++)
            {
                if(Q)
                {
                    if(Q > 1) dp[Q][W][E] = max(dp[Q][W][E], dp[Q-2][W][E] + v[1]);//QQ
                    if(W) dp[Q][W][E] = max(dp[Q][W][E], dp[Q-1][W-1][E] + v[2]);//QW
                    if(E) dp[Q][W][E] = max(dp[Q][W][E], dp[Q-1][W][E-1] + v[3]);//QE
                }
                if(W)
                {
                    if(Q) dp[Q][W][E] = max(dp[Q][W][E], dp[Q-1][W-1][E] + v[4]);
                    if(W > 1) dp[Q][W][E] = max(dp[Q][W][E], dp[Q][W-2][E] + v[5]);
                    if(E) dp[Q][W][E] = max(dp[Q][W][E], dp[Q][W-1][E-1] + v[6]);
                }
                if(E)
                {
                    if(Q) dp[Q][W][E] = max(dp[Q][W][E], dp[Q-1][W][E-1] + v[7]);
                    if(W) dp[Q][W][E] = max(dp[Q][W][E], dp[Q][W-1][E-1] + v[8]);
                    if(E > 1) dp[Q][W][E] = max(dp[Q][W][E], dp[Q][W][E-2] + v[9]);
                }
            }
        }
    }
    cout << dp[num[1]][num[2]][num[3]] + num[4] * v[10];
	return 0;
}

D

原题链接

做了好久的一题QAQ，虽然不难QAQAQAQAQAQ

最开始想的是第一层有些节点会被别的节点覆盖，所以只用遍历那些没有覆盖的节点即可；但是因为这些没有直接覆盖的节点可能在到达对岸的节点是有相互覆盖的，所以不能直接用没有覆盖的节点算作需要的工厂数

于是第二遍，我把第一行的所有结点都放进去bfs了一遍，很显然，TLE了

最后结合了第一种做法，并利用dfs递归找到每个起点对应的终点区间，贪心求解即可

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N];
int n, m;
int l[N][N], r[N][N];
int st[N][N];
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
void dfs(int i, int j)
{
	st[i][j] = 1;
	for (int t = 0; t < 4; t++)
	{
		int x = i + dx[t], y = j + dy[t];
		if (x >= 1 && y >= 1 && x << n && y <= m)
		{
			if (g[x][y] < g[i][j])
			{
				if (!st[x][y]) dfs(x, y);
				l[i][j] = min(l[i][j], l[x][y]);
				r[i][j] = max(r[i][j], r[x][y]);
			}
		}
	}
}
signed main()
{
	memset(l, 0x3f3f3f3f, sizeof l);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> g[i][j];
			if (i == n) l[i][j] = r[i][j] = j;
		}
	for (int i = 1; i <= m; i++)
		if (!st[1][i]) dfs(1, i);
	int cnt0 = 0, cnt1 = 0;
	for (int i = 1; i <= m; i++)
		if (!st[n][i]) cnt0++;
	if (cnt0) cout << 0 << '\n' << cnt0;
	else
	{
		int tl = 1, tr = r[1][1];
		while (tl <= m)
		{
			for (int i = 1; i <= m; i++)
			{
				if (l[1][i] <= tl)
					tr = max(tr, r[1][i]);
			}
			tl = tr + 1;
			cnt1++;
		}
		cout << 1 << '\n' << cnt1;
	}
	return 0;
}