HDU 5203 Rikka with wood sticks 分類讨論

題目連結：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5203

bc(chinese):http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=575&pid=1002

題解：

不斷的分類讨論下去

1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 const int maxn=1000+10;
 7 const int INF=0x3f3f3f3f;
 8 typedef long long LL; 
 9 
10 int n,m;
11 
12 int main(){
13     while(scanf("%d%d",&n,&m)==2&&n){
14         //找出bad stick的左右界限 
15         int beg=INF,end=-1;
16         for(int i=0;i<m;i++){
17             int x;
18             scanf("%d",&x);
19             beg=min(beg,x);
20             end=max(end,x);
21         }
22         int l1=beg-1,l2=n-end;
23         if(l1>l2) swap(l1,l2);
24         LL ans=0;
25          
26         if(l1>0){
27             //截取的bad stick段在中間 
28             for(int i=1;i<l2;i++){
29                 int a=l1,b=i,c=l2-i;
30                 if(a+b>c&&a+c>b&&b+c>a) ans++;
31             }
32         }else{
33             //截取的bad stick段在兩邊 
34             for(LL x=(l2+2)/3;x<(l2+1)/2;x++){
35                 //枚舉最長邊為x的情況 
36                 LL tmp=3*x+1-l2,cnt=0;//tmp代表第一條邊為x時的所有合法的情況（後兩條邊有考慮順序，第一條邊不考慮順序） 
37                 if(l2-2*x>0){
38                     //最長邊有可能存在兩條的情況 
39                     if(l2-2*x==x){
40                         //三條邊相等（x,x,x） 
41                         cnt=(tmp-1)*3+1;
42                     }else{
43                         if(((l2-x)&1)==0){
44                             //有兩條邊相等的情況（1、x,x,a(a<x)；2、x,a,a(a<x)) 
45                             cnt=(tmp-3)*3+3*1+3*1;
46                         }else{
47                             //（x,x,a） 
48                             cnt=(tmp-2)*3+3*1;
49                         }
50                     }
51                 }else{
52                     //最長邊不可能存在兩條的情況 
53                     if(((l2-x)&1)==0){
54                         //（ x,a,a） 
55                         cnt=(tmp-1)*3+3*1;
56                     }else{
57                         //（x,b,a(b!=a)）
58                         cnt=tmp*3;
59                     }
60                 }
61                 ans+=cnt;
62             }
63         }
64         printf("%lld\n",ans);
65     }
66     return 0;
67 }