2.21测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------------
感觉今天每道题都很有意思....
题意：
T1:给定n个点,每个点有一个颜色c[i]和代价cost[i],颜色不同的点i,j之间可以连边，产生的代价是cost[i]+cost[j]+100*|i-j|，求最小权(n-k)/2匹配（也就是删掉k个点后的点都要匹配，且代价最小）(n<=2500,c[i]<=6,k<=6)
T2:n个硬币排成一排，每个有一个面额，每一轮随机把每个硬币翻成正面或背面，一个硬币翻成正面的概率是常数p，每次选择编号最小的翻成正面的硬币删掉，如果全是背面就删掉第一个，获得的价值是这个硬币两边的硬币面值之积（如果是最边上的就没有价值），求这样进行n轮后（也就是删掉了所有硬币）期望价值(n<=300)
T3:n个人每个人有个权值，打乱这些人的位置，现在一个人可以花一的代价把他的一点权值给另一个人，问有多少种打乱方法，使得这些人通过交换权值变成原序列所需的最小代价刚好是k(n<=50,k<=650)
------------------------------------------------------------------
T1:
如果k=0的话，就有一个贪心：每次到达一个元素，如果栈中有不同类元素，那么他们一起消掉，否则这个元素入栈
因此栈中元素一定是是同一类型的（不是就消掉了）
因此可以DP:
f(i,j,k,v)表示前i个，当前栈中元素类型是j，有k个，跳过了v个
暴力转移就好
------------------------------------------------------------------
T2:
首先尝试考虑(i,j)这一对不相邻硬币产生贡献的概率，即某一种选法使得他们中间的点都被选完的概率
设f[l][mid][r]表示i左边有l个硬币,i,j中间有mid个硬币,j右边有r个硬币
初始f[i-1][j-i-1][n-j]=1
然后暴力转移一下
最后(i,j)产生贡献的概率是∑（l=1,n)∑(r=l,n)f[l][0][r],乘以他们的面额之积就是他们对答案的贡献
这样是n^5的，因为转移是n^3,而枚举(i,j)是O(n^2)的
考虑优化，因为我们每次都对所有硬币做一次DP，而最后的乘以的是他们产生的价值，再相加，因此最后可以对所有硬币同时DP，一开始先把f[i-1][j-i-1][n-j]赋成(i,j)的产生的贡献，换句话说用一次DP来求出最后的答案，因此是O(n^3)的
------------------------------------------------------------------
T3:
我考试时候想的：
先排序
显然有一个排列的的最小代价是这个排列每个元素减原排列对应元素（小于0则为0）的和
因此考虑a[i][j]表示i这个元素被分在了j这个位置产生的贡献
显然是要从a中选出一个权值和为k的SDR出来
然后...然后我就不会了...（我还不知道这个问题是否可解）(update:后来发现这个问题和哈密顿路径有关...GG)
标算：
先排序
总的代价是|ai-bi|/2,因此求|ai-bi|=2*k的情况数就行
设f(i,j,k,v)表示考虑了前i个,a前面还有j个小于ai的没确定位置,b前面还有k个空位，代价为v
现在假设把第i个元素放到第x个位置上
讨论一下这两个的大小关系，转移一下
这里要注意，在i这个地方要确定某一个标号小于i的元素的位置，因此i这个元素如果要放到后面的话，那么就认为他还没有确定，并且认为只有一种放法
------------------------------------------------------------------
评论 (0)
