首页 > ACM题库 > HDU-杭电 > HDU 1819 Bishops-计算几何-[解题报告] C++
2013
12-23

HDU 1819 Bishops-计算几何-[解题报告] C++

Bishops

问题描述 :

Yesterday was Sam’s birthday. The most interesting gift was definitely the chessboard. Sam quickly learned the rules of chess and defeated his father, all his friends, his little sister, and now no one wants to play with him any more.

So he decided to play with another birthday gift � a Book of Math Problems for Young Mathematicians. He opened the book somewhere in the middle and read the following problem: "How many knights can be placed on a chessboard without threatening each other?" After a while he realized that this was trivial and moved on to the next problem: "How many bishops can be placed on a chessboard without threatening each other?". Sam is in trouble here. He is not able to solve this problem and needs your help.

Task Specification

Sam’s chessboard has size N×N. A bishop can move to any distance in any of the four diagonal directions. A bishop threatens another bishop if it can move to the other bishop’s position. Your task is to compute the maximum number of bishops that can be placed on a chessboard in such a way that no two bishops threaten each other.

输入:

The input file consists of several lines. The line number i contains a single number representing the size( <10^100) of the i-th chessboard.

输出:

The output file should contain the same number of lines as the input file. The i-th line should contain one number � the maximum number of bishops that can be placed on i-th chessboard without threatening each other.

样例输入:

2
3

样例输出:

2
4

#include <iostream>
 #include <string.h>
 #include <string>
 #include <fstream>
 #include <algorithm>
 #include <stdio.h>
 #include <vector>
 #include <queue>
 #include <set>
 #include <cmath>
 using namespace std;
 const double eps = 1e-8;
 const double pi=acos(-1.0);
 const int INF=0x7fffffff;
 unsigned long long uINF = ~0LL;
 #define MAXN 1007
 #define mod 1000000007
 typedef long long LL;
 
 LL d1[33][1000],d2[33][1000];
 LL len1[33],len2[33];
 int n,k;
 void init()
 {
     len1[1]=len1[2]=1;
     len2[1]=len2[2]=2;
     for(int i=3;i<=30;i+=2)
     {
         len1[i]=len1[i+1]=len1[i-1]+2;
         len2[i]=len2[i+1]=len2[i-1]+2;
     }
 }
 //D[i,j] = (Len[i]-j+1)*D[i-1,j-1] + D[i-1,j]
 int main()
 {
     //freopen("0.in","r",stdin);
     init();
     while(scanf("%d%d",&n,&k),n+k!=0)
     {
         memset(d1,0,sizeof(d1));
         memset(d2,0,sizeof(d2));
 
         for(int i=0;i<=n;i++)
         {
             d1[i][0]=1;d2[i][0]=1;
         }
 
         for(int i=1;i<=n;i++)
         for(int j=1;j<=k;j++)
         {
             d1[i][j]=(len1[i]-j+1)*d1[i-1][j-1]+d1[i-1][j];
             if(i!=n)d2[i][j]=(len2[i]-j+1)*d2[i-1][j-1]+d2[i-1][j];
         }
 
         LL ans=0;
         for(int i=0;i<=k;i++)
         ans+=d1[n][i]*d2[n-1][k-i];
         printf("%lld\n",ans);
     }
 
     return 0;
 }
D[i,j] = (Len[i]-j+1)*D[i-1,j-1] + D[i-1,j]
对棋盘染色 跟国际象棋的棋盘一样 分成两部分 旋转45° 后 分别dp
ans=d[n][i]+d[n-1][k-i];

解题报告转自:http://www.cnblogs.com/TO-Asia/p/3219208.html