【poj 3056】The Bavarian Beer Party (区间DP+最大匹配不交叉的简单算法)
题目大意:一组数按照顺时针排列,数值相同的两个位置可以连一条线,最终线与线不交叉的最大数量为多少。 这道题目是求最大匹配的题目,初学区间DP,脑子一片空白,仅仅记下来,以供之后温习。 按照区间的想法可以很容易的得到,dp[i][j]所存的是i到j当中满足条件的最大数值,那么有dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]); 这个是解决在i到j区间当中有两部分连…