题解其实网上有 突然有点感想 为什么可以用搜索或状压，因为方案数很有限，它要求每种方案不同就意味着搜索的次数也一定，所以现在就应该坚定往这方面想，找部分方案的贪心。这和上一题一样，都是先暴力，后面处理。
#include<bits/stdc++.h> using namespace std; #define sz(X) ((int)X.size()) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; const int INF = 0x3f3f3f3f; const int N = 1e5+5; int num[15]; int X[15], Y[15], Z[15]; int ans, tmp; int ok(int x, int nu) { if(nu == 0) return 1; else if(X[x] == Y[x]) { if(num[X[x]] >= 2*nu && num[Z[x]] >= nu) return 1; }else if(num[X[x]] >= nu && num[Y[x]] >= nu && num[Z[x]] >= nu) return 1; return 0; } int cal(){ // printf("%d: ",tmp); for(int i = 1; i <= 9; ++i) printf("%d ",num[i]); int ret = 0; int pre[10]; for(int i = 1; i <= 9; ++i) pre[i] = num[i]; for(int i = 2; i <= 8; ++i) { int mi = min(2, min( num[1], min(num[i], num[i+1]) ) ); num[1] -= mi; num[i] -= mi; num[i+1] -= mi; ret += mi; if(num[1] == 0) break; } for(int i = 1; i <= 9; ++i) num[i] = pre[i]; return ret; } void dfs(int x, int pr) { if(pr) { int tt = cal(); tmp += tt; ans = max(tmp, ans); tmp -= tt; } if(x > 13) return; int ed; if(x < 10) ed = 2; else ed = 1; for(int i = 0; i <= ed; ++i) { if(ok(x,i)) { num[X[x]] -= i; num[Y[x]] -= i; num[Z[x]] -= i; tmp += i; dfs(x+1, i); num[X[x]] += i; num[Y[x]] += i; num[Z[x]] += i; tmp -= i; } } } int main(){ int cc = 0; for(int i = 2; i <= 9; ++i) for(int j = i+1; j <= 9; ++j) { if(i+j <= 9) { X[++cc] = i; Y[cc] = j; Z[cc] = i+j; } } for(int i = 10; i <= 13; ++i) { X[i] = i-9; Y[i] = i-9; Z[i] = Y[i]+X[i]; } int _; scanf("%d",&_); for(int cas=1; cas<=_; ++cas) { for(int i = 1; i <= 9; ++i) scanf("%d",&num[i]); ans = cal(); tmp = 0; dfs(1, 0); printf("Case #%d: %d\n",cas,ans); } return 0; }转载于:https://www.cnblogs.com/Basasuya/p/8433730.html
