dfs_enumeration_partition

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

CCPC-Wannafly Winter Camp Day2 (Div1, online mirror) Sticks

题目大意 :
        给你12根棍子，让你对棍子分四堆，每堆三根， 要求这四堆棍子尽可能组成多的三角形

         解法1:考虑到划分只有3万个左右，实际上dfs枚举划分就可以ac。详见代码
         解法2:考虑分块，先分成6+6，有接近1000种分法，然后6=3+3，6=3+3，但是我们有必要用一边的6=3+3 的所有划分去匹配另一边的6=3+3的划分吗？其实不需要，我们只需要单独考虑两边的6=3+3，取最优分法 然后组合在一起，因为互不影响，所以可以直接最优对最优，省掉了很大一部分的讨论，复杂度为12=6+6的 划分的种类数乘以2再乘以6=3+3的划分的种类数大概为2万，相比解法1优化了一部分常数。
        我使用解法2的代码很蠢很长，就不拿出来了。

#include<bits/stdc++.h>
using namespace std;

int dfs(int*a,int n){
    if(n==3)return a[0]+a[1]>a[2];
    
    int ret=0,ret_array[12]{};
    int b[12],b_=0;
    
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++){
            b_=0;
            for(int k=1;k<n;k++){
                if(k==i||k==j)continue;
                b[b_++]=a[k];
            }
            int tmp=dfs(b,n-3);
            if(tmp+(a[0]+a[i]>a[j])>ret){
                ret=tmp+(a[0]+a[i]>a[j]);
                memcpy(ret_array,b,sizeof(int)*(n-3));
                ret_array[n-3]=a[0];
                ret_array[n-2]=a[i];
                ret_array[n-1]=a[j];
            }
        }
    }
    memcpy(a,ret_array,sizeof(int)*n);
    return ret;
}

int main(){
    int a[12],T;
    scanf("%d",&T);
    
    for(int times=1;times<=T;times++){
        for(int i=0;i<12;i++)scanf("%d",a+i);
        sort(a,a+12);
        int ans=dfs(a,12);
        printf("Case #%d: %d\n",times,ans);
        for(int i=0;i<12;i+=3){
            if(a[i]+a[i+1]>a[i+2]){
                printf("%d %d %d\n",a[i],a[i+1],a[i+2]);
            }
        }
    }
}