POJ2137——Cowties

Cowties
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 2870
 
Accepted: 961
Description
N cows (3 <= N <= 100) are eating grass in the middle of a field. So that they don't get lost, Farmer John wants to tie them together in a loop so that cow i is attached to cows i-1 and i+1. Note that cow N will be tied to cow 1 to complete the loop.
Each cow has a number of grazing spots she likes and will only be happy if she ends up situated at one of these spots. Given that Farmer John must ensure the happiness of his cows when placing them, compute the shortest length of rope he needs to tie them all in a loop. It is possible for different parts of the loop to cross each other.
Input
* Line 1: The integer N.
* Lines 2..N+1: Each line describes one cow using several space-separated integers. The first integer is the number of locations S (1 <= S <= 40) which are preferred by that cow. This is followed by 2*S integers giving the (x,y) coordinates of these locations respectively. The coordinates lie in the range -100..100.
Output
A single line containing a single integer, 100 times the minimum length of rope needed (do not perform special rounding for this result).
Sample Input

4
1 0 0
2 1 0 2 0
3 -1 -1 1 1 2 2
2 0 1 0 2

Sample Output

400

Hint
[Cow 1 is located at (0,0); cow 2 at (1,0); cow 3 at (1,1); and cow 4 at (0,1).]
Source
USACO 2003 February Orange
n 마리 소, 모든 소는 제한된 방목 구역을 가지고 n 마리 소에게 방목 구역을 잘 배정한 후에 그들 사이의 가장 짧은 거리(하나의 고리를 형성한다)
뚜렷한dp,하지만 머리와 꼬리가 맞닿아 있기 때문에 단순히 1매에서 n까지 일일이 들 수 없습니다. 처음에 저는 이렇게 한 다음에wa를 2번 했습니다. 밤에 잠을 잘 때 이것을 생각하고 1이 소의 방목 가능한 구역을 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 n까지 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일이 일일

#include <map>  
#include <set>  
#include <list>  
#include <stack>  
#include <vector>  
#include <queue>  
#include <cmath>  
#include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  

using namespace std;

double dp[110][50];

vector<pair<int, int> >pp[110];

double dist(int x1, int y1, int x2, int y2)
{
	return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) );
}

int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		int cnt, x, y;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &cnt);
			for (int j = 0; j < cnt; ++j)
			{
				scanf("%d%d", &x, &y);
				pp[i].push_back( make_pair(x, y) );
			}
		}
		memset (dp, 0, sizeof(dp) );
		double ans = 0x3f3f3f3f;
		int fc = pp[1].size();
		for (int i = 0; i < fc; ++i) //      
		{
			int sc = pp[2].size();
			for (int p = 0; p < sc; ++p)
			{
				dp[2][p] = dist(pp[1][i].first, pp[1][i].second, pp[2][p].first, pp[2][p].second);
			}
			for (int j = 3; j <= n; ++j)
			{
				int tc = pp[j].size();
				for (int k = 0; k < tc; ++k)
				{
					int ffc = pp[j - 1].size();
					double mins = 0x3f3f3f3f;
					 for (int q = 0; q < ffc; ++q)
					 {
					 	mins = min(mins, dp[j - 1][q] + dist(pp[j - 1][q].first, pp[j - 1][q].second, pp[j][k].first, pp[j][k].second));
					 }
					 dp[j][k] = mins;
					 if (j == n)
					{
						ans = min(ans, dp[n][k] + dist(pp[n][k].first, pp[n][k].second, pp[1][i].first, pp[1][i].second));	
					}
				}
			}
		}
		printf("%d
", int(ans * 100));
	}
	return 0;
}