2014
02-14

# Wooden Fence

Did you ever wonder what happens to your money when you deposit them to a bank account? All banks hold such deposits in various assets, such as gold, stocks, obligations, deposits in other banks, loans, bonds, and many others. Due to the financial crisis and instability of the stock exchanges, many banks find out that stocks are not very reliable and their possession may be too risky.

Therefore, the banks now prefer other assets, especially gold. The main trouble with gold is that there is only a limited amount of it in the whole world. And it is not enough to cover all money held by all banks. (Wait, isn’t this the real reason of the crisis?)

If there is not enough gold, other commodities must be exploited instead. The International Bank of Monetania (IBM) has recently come up with an idea of using very old and valuable trees as their assets. They bought a piece of land with several such trees and now expect their value to grow. Literally, of course.

Unfortunately, the trees are threatened by wildlife, because animals do not understand their value and nibble them. Moreover, there is a permanent danger of theft. As a result, it is absolutely necessary to build a good solid fence around the trees.

The IBM quickly realized that the only suitable material available to build the fence is the wood from the trees themselves. In other words, it is necessary to cut down some trees in order to build a fence around the remaining ones. Of course, to keep the maximum value, we want to minimize the value of the trees that had to be cut. You are to write a program that solves this problem.

The input contains several test cases, each of which describes one piece of land. Each test case begins with a line containing a single integer N, 2 ≤ N ≤ 16, the total number of trees. Each of the subsequent N lines contains 4 integers Xi, Yi, Vi, Li separated by at least one space.

The four numbers describe a single tree. (Xi, Yi) is the position of the tree in the plane, Vi is its value, and Li is the length of fence that can be built using the wood of the tree. You may assume that 0 ≤ Vi, Li ≤ 10000 and -10000 ≤ Xi, Yi ≤ 10000. No two trees in a test case will grow at the same position.

The input ends with a line containing zero in place of N.

The input contains several test cases, each of which describes one piece of land. Each test case begins with a line containing a single integer N, 2 ≤ N ≤ 16, the total number of trees. Each of the subsequent N lines contains 4 integers Xi, Yi, Vi, Li separated by at least one space.

The four numbers describe a single tree. (Xi, Yi) is the position of the tree in the plane, Vi is its value, and Li is the length of fence that can be built using the wood of the tree. You may assume that 0 ≤ Vi, Li ≤ 10000 and -10000 ≤ Xi, Yi ≤ 10000. No two trees in a test case will grow at the same position.

The input ends with a line containing zero in place of N.

6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8
3
3 0 10 3
5 -3 20 25
7 -3 30 32
2
100 0 5 4
0 100 4 5
5
0 0 10 10
0 1 10 10
1 0 10 10
1 1 10 10
50 50 8 4
0

The lost value is 9.
The lost value is 20.
The lost value is 4.
The lost value is 8.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N=250;
const int MOD=1000000007;

struct data
{
int type;
int width, length;
} a[N];

int f[3050][250], n, cnt, m;

int main()
{
memset(f, 0, sizeof(f));
scanf("%d%d", &n, &m);
cnt=n;
for(int i=1, L, W; i<=cnt; i++)
{
scanf("%d%d", &L, &W);
a[i].length=L, a[i].width=W, a[i].type=i;
f[L][i]=(f[L][i]+1)%MOD;
if(L!=W)
{
n++;
a[n].length=W, a[n].width=L, a[n].type=i;
f[W][n]=(f[W][n]+1)%MOD;
}
}
for(int L=0; L<=m; L++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(a[i].type!=a[j].type && a[j].width==a[i].length && L>=a[i].length)
{
f[L][i]=(f[L][i]+f[L-a[i].length][j])%MOD;
}
int ans=0;
for(int i=1; i<=n; i++)
ans=(ans+f[m][i])%MOD;
printf("%d\n", ans);
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。