1.先加后乘

题意：目的找到3个数字,使得 ，输出 。

题解：注意数据范围，故 的遍历明显不能通过此题。此时先给数组进行一个排序。 我知道很多人会想 秒了!很可惜忽略了题目中的另一个数据范围：每个整数的绝对值不超过 。 你们看到绝对值三个字都不会细铐（不细心就得接受拷打）一下的吗？So，我们需要考虑一下有0和负数的情况。

需要分类讨论：

  1. 全部是正数（包括0）的情况
  2. 全部是负数（包括0）的情况
  3. 答案为1负2正的情况
  4. 答案为2负1正的情况

写if else太辛苦了，干脆让用 让计算机算几种里面最小的即为答案。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
	int n,cnt0=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	sort(a,a+n);
	for(int i=0;i<n;i++){
		if(a[i]==0)cnt0++;
	}
	int ans=10000*20000;
	ans=min({ans,a[0]*(a[1]+a[2]),a[0]*(a[n-1]+a[n-2]),(a[0]+a[1])*a[n-1],(a[n-3]+a[n-2])*a[n-1]});
	if(cnt0)ans=min(0,ans);
	printf("%d",ans); 
}

2.异画师的技能组合-1

题意：题目很长，简单来说就是按下QWE中的任意一个都会进入就绪状态，按R可以取消施法，就绪状态再按QWE中的任何一个就会释放，单独按R能放大，给你10个技能的得分。请你根据按键顺序计算总的得分。

题解：只需要按照题目意思模拟即可。

代码：

#include<bits/stdc++.h>
using namespace std;
map<string, int>mp;

int main()
{
	cin >> mp["QQ"];
	cin >> mp["QW"];
	cin >> mp["QE"];
	cin >> mp["WQ"];
	cin >> mp["WW"];
	cin >> mp["WE"];
	cin >> mp["EQ"];
	cin >> mp["EW"];
	cin >> mp["EE"];
	cin >> mp["R"];
	char c;
	string str;
	int ans = 0;
	while (cin >> c)
	{
		if (c == 'R')
		{
			if (str.size() == 1)
			{
				str.pop_back();
			}
			else
			{
				ans += mp["R"];
			}
		}
		else
		{
			str += c;
			if (str.size() == 2)
			{
				ans += mp[str];
				str.clear();
			}
		}
	}
	cout << ans;
	return 0;
}

3.异画师的技能组合-2

题意：前提条件同上，题目变成给你每个按键能按多少下，求最大得分。

题解：是一个很典的多重背包dp，注意就绪状态就行。

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[150][150][150];

void work() {
    int v[15], num[5];
    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]);
                    if (W) dp[Q][W][E] = max(dp[Q][W][E], dp[Q - 1][W - 1][E] + v[2]);
                    if (E) dp[Q][W][E] = max(dp[Q][W][E], dp[Q - 1][W][E - 1] + v[3]);
                }
                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];
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) {
        work();
    }
    return 0;
}

4.北水南调

题意：

题解：易证：如果有解，则每个水厂能覆盖的城市一定是连续的。 先对第一行的每一个位置都dfs一下，记录它所覆盖的城市的左右边界，并且将能到达城市（最后一行）都标记一下。 计算标记的数量可知是否有解。 然后对于最后一行进行贪心即可求得最少水厂数。贪心策略是从左往右选取覆盖面积最长的水厂，且保证该水厂的左边界在已覆盖的区域内。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N = 505;
int n, m;
int mp[N][N], l[N][N], r[N][N];
bool book[N][N];
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
void dfs(int x,int y)
{
	book[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if (tx >= 1 && tx <= n && ty >= 1 && ty <= m)
		{
			
			if (mp[x][y] > mp[tx][ty])
			{
				if(book[tx][ty]==0)
				dfs(tx, ty);
				l[x][y] = min(l[x][y], l[tx][ty]);
				r[x][y] = max(r[x][y], r[tx][ty]);
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	memset(l, 1000005, sizeof(l));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> mp[i][j];
			if (i == n)
			{
				l[i][j] = r[i][j] = j;
			}
		}
	}
	
	for (int i = 1; i <= m; i++)
	{
		if (!book[1][i])
		{
			dfs(1, i);
		}
	}
	int key = 0;
	int ans = 0;
	for (int i = 1; i <= m; i++)
	{
		if (book[n][i] == 0)
		{
			key++;
		}
	}
	if (key)
	{
		cout << 0 << endl << key << endl;
	}
	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;
			ans++;
		}
		cout << 1 << endl << ans << endl;
	}
}