poj-3056 http://poj.org/problem?id=3056

http://poj.org/problem?id=3056

The Bavarian Beer Party
Time Limit: 6000MS   Memory Limit: 65536K
Total Submissions: 995   Accepted: 359

Description

The professors of the Bayerische Mathematiker Verein have their annual party in the local Biergarten. They are sitting at a round table each with his own pint of beer. As a ceremony each professor raises his pint and toasts one of the other guests in such a way that no arms cross. 
poj-3056                              http://poj.org/problem?id=3056 
Figure 2: Toasting across a table with eight persons:no arms crossing(left), arms crossing(right)

We know that the professors like to toast with someone that is drinking the same brand of beer, and we like to maximize the number of pairs of professors toasting with the same brand , again without crossing arms. Write an algorithm to do this, keeping in mind that every professor should take part in the toasting.

Input

The frist line of the input contains a single number: the number of test cases to follow. Each test case has the following format: 
One line with an even number p, satisfying 2 <= p <= 1000: the number of participants 
One line with p integers (separated by single spaces) indicating the beer brands fro the consecutive professors( in clockwise order, starting at an arbitrary position). Each value is between 1 and 100 (boudaries included).

Output

For every test case in the input, the output should contain a single number on a single line: the maximum number of non-intersecting toasts of the same beer brand for this test case.

Sample Input

2
6
1 2 2 1 3 3
22
1 7 1 2 4 2 4 9 1 1 9 4 5 9 4 5 6 9 2 1 2 9

Sample Output

3
6
题意:
题意:有偶数个人,所有人都必须互相敬酒,而且不能交叉,问在这种情况下,互相敬酒的人牌子相同的最大对数
d[i][j]表示第i个数到第j个数最大配对数
状态转移方程:

if(a[i]==a[j])
                    dp[i][j]=dp[i+1][j-1]+1;
                else
                    dp[i][j]=dp[i+1][j-1];d[i][j]=max(d[i][j],d[i][k]+d[k+1][j])          (i<=k<j)

主要注意的是:要解决不能交叉,而且每个教授都要敬酒,所以两头尾之间相隔的的人数必须为0,2,4..等偶数。

怎样控制区间之间是偶数呢?
for(k=1;k<=m;k+=2)
如果for(k=0;k<m;k+=2),那么就会控制区间之间为奇数。
试试就知道了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[][];
int main()
{
int i,j,k,m,t,a[],g;
cin>>t;
while(t--)
{
memset(dp,,sizeof(dp));
cin>>m;
for(i=;i<m;i++)
cin>>a[i];
for(k=;k<=m;k+=)//因为不能交叉,
//所以两头尾之间相隔的的人数必须为0,2,4..等偶数
//如果for(k=0;k<m;k+=2),那么就会控制区间之间为奇数。
{
for(i=;i<m-k;i++)
{
j=i+k;
if(a[i]==a[j])
dp[i][j]=dp[i+][j-]+;
else
dp[i][j]=dp[i+][j-];
for(g=i;g<j;g++)
dp[i][j]=max(dp[i][j],dp[i][g]+dp[g+][j]);//分割区间求最优。 }
}
cout<<dp[][m-]<<endl;
}
return ;
}


上一篇:Android Support Library控件详细介绍之RecyclerView


下一篇:最小生成树 10.1.5.253 1505 poj 1258 http://poj.org/problem?id=1258