8076,8593,8595,8518

T1

快排+贪心
要美味之和尽可能大，那么对红色和绿色苹果按美味值从大到小排序，红色取出X个，绿色取出Y个，放入到无色苹果堆中，再按从大到小排序，取前X+Y个。

T2

模拟
如果纯模拟，那么肯定会超时，因为$1\le H,W\le 1500$，枚举灯泡位置，再朝4个方向统计，时间复杂度为$O(H\ast W\ast max(H,W))={1500}^3$。
所以这题不能这样去模拟，我们可以把4个方向拆成两部分：左右和上下。
从左往右的思路：判断当前是灯泡、障碍物、空地，如果是灯泡，辅助数组记录点亮状态（显然原数组上是不能操作的，会无法区分灯泡还是被照亮），同时用变量记录当前格子的状态（亮或灭），因为其他格子也不能根据周围的格子（辅助数组的状态）做递推，会误判。
所以最好的做法是记录上一次的状态是什么，灯光照过来还是没照过来。
给出左边模拟代码，右边和上下都类似。

	for(int i = 1; i <= h; i++){ //按行处理
		bool tag = 0;  //记录最后一次的状态：有光或无光
		for(int j = 1; j <= w; j++){ //从左往右
			if(Grid[i][j]==1) vis[i][j] = 1, tag = 1; //有光
				else if(Grid[i][j]==-1) tag = 0; //无光
				else vis[i][j] = vis[i][j] || tag; //布尔值可以用逻辑运算
		}
		tag = 0;
		for(int j = w; j >= 1; j--){ //从右往左
            ...			
		}
	}

虽是模拟题，但要考虑时间复杂度，如果不细想，是不可能想到拆开来模拟，上面的算法，时间复杂度降为$O(HW)={1500}^2$

T3

DFS
学算法，要掌握算法特征。
这题看到的时候难道想不起慈溪市的传话游戏？难道想不起慈溪市的工作分配问题？

void dfs(城市编号,当前旅行时间){
    if(城市编号==1 并且 当前城市已访问){
         判断是否符合要求
    }else for(枚举跟当前城市相连的城市){
            if(枚举的城市编号没访问过){
                标记;
                dfs(新的城市编号,当前旅行时间+新访问城市的时间);
                取消标记;
            }
    }
}

T4

DP
过河卒变形题。
有了数量限制，所以状态设计为$dp[i][j][k]$，$k$表示数量限制，$0\le k\le 3$。
加了限制后，要枚举所有的状态，双重循环不够用，需要三重循环（加一层数量枚举）
现在我们来思考转移方程，对$dp[i][j][k]$来说，可以从上面转移过来：$dp[i-1][j][3]+a[i][j]$，为什么是$dp[i-1][j][3]$？因为价值要最大，在$dp[i-1][j][1]$、$dp[i-1][j][2]$、$dp[i-1][j][3]$中，显然$dp[i-1][j][3]$价值肯定最大，它表示第$i-1$行前j个物品中拿3个物品的最大价值。
而左边转移过来有两种情况：$dp[i-1][j][k]$和$dp[i-1][j][k-1]+a[i][j]$，前一个状态表示不拿当前位置的物品，后一个表示拿当前物品，注意数量的计算。
综上所述，状态转移方程为：

dp[i][j][k]=max(dp[i-1][j][3] + a[i][j], max(dp[i][j-1][k - 1] + a[i][j], dp[i][j-1][k]));