2013
11-10

# The Happy Worm

The Happy Worm lives in an m*n rectangular field. There are k stones placed in certain locations of the field. (Each square of the field is either empty, or contains a stone.) Whenever the worm sleeps, it lies either horizontally or vertically, and stretches so that its length increases as much as possible. The worm will not go in a square with a stone or out of the field. The happy worm can not be shorter than 2 squares.

The question you are to answer is how many different positions this worm could be in while sleeping.

The first line of the input contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The first line of each test case contains three integers m, n, and k (1 <= m,n,k <= 131072). The input for this test case will be followed by k lines. Each line contains two integers which specify the row and column of a stone. No stone will be given twice.

There should be one line per test case containing the number of positions the happy worm can be in.

1
5 5 6
1 5
2 3
2 4
4 2
4 3
5 1


9

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

public static final int MAX = 152;
static List< Integer> v[];
static int dp[][];
static int p;
static int root;

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();
p = scan.nextInt();

boolean s[] = new boolean[n+1];
v = new ArrayList[n+1];
java.util.Arrays.fill(s, true);
dp = new int[n+1][p+1];

for(int i=0;i<=n;i++)
java.util.Arrays.fill(dp[i], MAX);

for(int i=1;i<=n;i++)
v[i] = new ArrayList< Integer>();

for(int i=1;i< n;i++){
int u = scan.nextInt();
int t = scan.nextInt();
s[t] = false;
}

for(int i=1;i<=n;i++){
if(s[i]){
root = i;
dfs(root);
break;
}
}

int ans = MAX;
for(int i=1;i<=n;i++)
ans = Math.min(ans,dp[i][p]);

System.out.println(ans);

}

public static void dfs(int u) {

for(int i=0;i< v[u].size();i++){

dfs(v[u].get(i));

}

if(u == root)
dp[u][1] = v[u].size();
else
dp[u][1] = v[u].size()+1;

for(int i=0;i< v[u].size();i++){
for(int j=p-1;j>=1;j--){
if(dp[u][j]< MAX){
for(int k=1;k+j<=p;k++){
if(dp[u][k]< MAX){
dp[u][j+k] = Math.min(dp[u][j+k], dp[u][j]+dp[v[u].get(i)][k]-2);//每次加一个子树 更新d[u][2..P]
}
}
}
}
}

}

}

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

3. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。