随笔 - 87  文章 - 279  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214327
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

Dominoes
Time Limit:1000MS  Memory Limit:65536K
Total Submit:1022 Accepted:333

Description
A domino is a flat, thumbsized tile, the face of which is divided into two squares, each left blank or bearing from one to six dots. There is a row of dominoes laid out on a table:


The number of dots in the top line is 6+1+1+1=9 and the number of dots in the bottom line is 1+5+3+2=11. The gap between the top line and the bottom line is 2. The gap is the absolute value of difference between two sums.

Each domino can be turned by 180 degrees keeping its face always upwards.

What is the smallest number of turns needed to minimise the gap between the top line and the bottom line?

For the figure above it is sufficient to turn the last domino in the row in order to decrease the gap to 0. In this case the answer is 1.
Write a program that: computes the smallest number of turns needed to minimise the gap between the top line and the bottom line.

Input
The first line of the input contains an integer n, 1 <= n <= 1000. This is the number of dominoes laid out on the table.

Each of the next n lines contains two integers a, b separated by a single space, 0 <= a, b <= 6. The integers a and b written in the line i + 1 of the input file, 1 <= i <= 1000, are the numbers of dots on the i-th domino in the row, respectively, in the top line and in the bottom one.

Output
Output the smallest number of turns needed to minimise the gap between the top line and the bottom line.

Sample Input

4
6 1
1 5
1 3
1 2

Sample Output

1

Source
CEOI 1997

#include  < iostream >
using   namespace  std;

const   int  MAXN  =   8000 ;
const   int  INF  =   1   <<   28 ;

struct  DATA  {
    
int  da[MAXN];
    
int  dx;
    
int  q;
}
;

DATA dp[
2 * MAXN];
bool  f[ 2 * MAXN];
int  queue[MAXN], front, rear;
int  main()
{
    
int  n;
    
int  a[MAXN], x, y;
    
int  i, j, k, w, l;
    
int  d  =   0 ;
    
int  ans  =  INF;
    scanf(
" %d " & n);
    
for  (i = 0 ; i < n; i ++ {
        scanf(
" %d%d " & x,  & y);
        a[i] 
=  x  -  y;
        d 
+=  a[i];
    }

    memset(f, 
false sizeof (f));
    dp[d
+ 7500 ].dx  =  d; dp[d + 7500 ].q  =   0 ; f[d + 7500 =   true ;
    
for  (i = 0 ; i < n; i ++ ) dp[d + 7500 ].da[i]  =  a[i];
    front 
=   0 ; rear  =   0 ; w  =   0 ;
    
do   {
        
for  (i = 0 ; i < n; i ++ {
            j 
=  dp[d + 7500 ].da[i];
            k 
=  d   -  j  *   2 ;
            
if  ( ! f[k + 7500 ||  dp[k + 7500 ].q  >  w  +   1 {
                
if  (k  ==   0 {
                    printf(
" %d\n " , w  +   1 );
                    system(
" pause " );
                    
return   0 ;
                }

                f[k
+ 7500 =   true ;
                queue[rear
++ =  k;
                dp[k
+ 7500 ].dx  =  k;
                dp[k
+ 7500 ].q  =  w  +   1 ;
                
for  (l = 0 ; l < n; l ++ ) dp[k + 7500 ].da[l]  =  dp[d + 7500 ].da[l];
                dp[k
+ 7500 ].da[i]  =   - dp[d + 7500 ].da[i];
            }

        }

        d 
=  queue[front ++ ];
        w 
=  dp[d + 7500 ].q;
    }
  while  (front  <=  rear);  
    j 
=   7500 ;
    
bool  isFind  =   false ;
    
for  (i = 0 ; i < 7500 ; i ++ {
        
if  (f[j + i])  {
            isFind 
=   true ;
            
if  (ans  >  dp[j + i].q) ans  =  dp[j + i].q;
        }

        
if  (f[j - i])  {
            isFind 
=   true ;
            
if  (ans  >  dp[j - i].q) ans  =  dp[j - i].q;
        }

        
if  (isFind)  break ;
    }

    printf(
" %d\n " , ans);
    system(
" pause " );
    
return   0 ;
}

posted on 2006-10-29 20:42 阅读(792) 评论(0)  编辑 收藏 引用 所属分类: ACM题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理