2013
12-21

# Number Sequence

Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

6
-1

/*
* 1711_2.cpp
*
*  Created on: 2013年7月30日
*/

#include <stdio.h>
#include <string.h>
#define N 50
//int max(int a , int b){
//	return (a>b)?a:b;
//}
//
//int min(int a ,int b){
//	return (a>b)?b:a;
//}
int max(int a ,int b){
return (a > b)?a:b;
}

int min(int a ,int b){
return (a > b)?b:a;
}

int f[N*N*N + 5],c[N+5],amount[N+5],V ;

void ZeroOnePack(int cost,int weight)
{
int j;
for(j=V;j>=cost;j--){
f[j]=max(f[j],f[j-cost]+weight);
}
}

void CompletePack(int cost , int weight){
int v;
for( v = cost ; v <=V  ; v++){//不要写成v--，否则会造成程序异常终止。而且很难调
f[v] = max(f[v],f[v-cost] + weight);
}

}
void MultiplePack(int cost ,int weight , int amount){
if(cost*amount >= V){
CompletePack(cost,weight);
return ;
}
int k = 1;
while( k < amount){
ZeroOnePack(k*cost,k*weight);
amount -= k;
k=k*2;
}
ZeroOnePack(amount*cost,amount*weight);
}

int main(){

int i,n,sum ;

while(scanf("%d",&n),n >= 0){

sum = 0;
for( i = 0 ; i < n ; ++i){
scanf("%d%d",&c[i],&amount[i]);

sum +=  c[i]*amount[i];
}

V = sum/2;
memset(f,0,sizeof(f));

for( i = 0 ; i < n ; ++i ){
MultiplePack(c[i],c[i],amount[i]);

}
printf("%d %d\n",max(f[V],sum-f[V]),min(f[V],sum - f[V]));

}
return 0;
}

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3