TCO09 Round 3
Level One SaveTheTrees
平面上有n棵树,每砍条一棵树,都会产生a[i]的木材。现在要用砍下来的木头围成长方形(边平行于坐标轴)木兰,围住剩下的
所有的树。问至少要砍掉多少棵树。(n<=40)
Level Two CampaignTrail
一个国家要选总统,获得超过半数的选票就才赢得选举。每个州的投票是依次进行的,如果你赢得某个州的选举,就能赢得这个州的全部选票。你最多可以在k个州进行演讲,你已知你在每个州演讲的话胜率是多少,不演讲的话在这个州胜率是多少。当然,因为投票不是同时进行的,所以你可以在第一个州投票结果出来以后,在决定是否在第二个州演讲。问,最后的当选的概率是多少?(州数<=50,每个州的选票<=50)
Level Three YetAnotherStonesGame
一种游戏在n个连成环的格子中进行,其中一些格子被标记为障碍。现在,由你放上若干个棋子,每次都可以选择一个棋子,顺时针的跳若干个格子,但是这个步数必须在输入的集合A中。要求,每一枚棋子要回到自己的原处,每一个非障碍的格子只能被经过总共恰好一次(作为起点的格子因此就不能被经过)。问至少要放多少枚棋子可以满足条件。(n<=50,A[i]<=6)
Solution
Level One SaveTheTrees 枚举举行的左下角顶点,上边界从上往下扫,总时间复杂度O(n^3)。
Level Two CampaignTrail DP反推。dp[i][j][k]表示前i个州要演讲j个州现在已经赢得k张选票的情况下的胜率。
Level Three YetAnotherStonesGame 枚举要用几枚棋子,每枚棋子走几圈。注意,总圈数不超过六。状态压缩。时间复杂度O(n*2^10)。
Level One SaveTheTrees
平面上有n棵树,每砍条一棵树,都会产生a[i]的木材。现在要用砍下来的木头围成长方形(边平行于坐标轴)木兰,围住剩下的
所有的树。问至少要砍掉多少棵树。(n<=40)
Level Two CampaignTrail
一个国家要选总统,获得超过半数的选票就才赢得选举。每个州的投票是依次进行的,如果你赢得某个州的选举,就能赢得这个州的全部选票。你最多可以在k个州进行演讲,你已知你在每个州演讲的话胜率是多少,不演讲的话在这个州胜率是多少。当然,因为投票不是同时进行的,所以你可以在第一个州投票结果出来以后,在决定是否在第二个州演讲。问,最后的当选的概率是多少?(州数<=50,每个州的选票<=50)
Level Three YetAnotherStonesGame
一种游戏在n个连成环的格子中进行,其中一些格子被标记为障碍。现在,由你放上若干个棋子,每次都可以选择一个棋子,顺时针的跳若干个格子,但是这个步数必须在输入的集合A中。要求,每一枚棋子要回到自己的原处,每一个非障碍的格子只能被经过总共恰好一次(作为起点的格子因此就不能被经过)。问至少要放多少枚棋子可以满足条件。(n<=50,A[i]<=6)
Solution
Level One SaveTheTrees 枚举举行的左下角顶点,上边界从上往下扫,总时间复杂度O(n^3)。
Level Two CampaignTrail DP反推。dp[i][j][k]表示前i个州要演讲j个州现在已经赢得k张选票的情况下的胜率。
Level Three YetAnotherStonesGame 枚举要用几枚棋子,每枚棋子走几圈。注意,总圈数不超过六。状态压缩。时间复杂度O(n*2^10)。