HDU 5937 Equation (搜索,贪心)

给出1~9数字的个数，求最多能构成多少个不同的等式，x + y = z，x、y、z都是一位数字，1 + 2 = 3 和 2 + 1 = 3算不同的式子。

对于1 + 2，1 + 3 … 1 + 8，这些式子可以贪心的取，能取的就取，那么剩下的式子有18个x != y的式子，4个x == y的式子，对于x != y的式子可以考虑将1 + 2 和 2 + 1这样的式子一起考虑，那么就是3 ^ 9 * 2 ^ 4，加上贪心的judge，那么总复杂度是O(3 ^ 9 * 2 ^ 4 * 9 * T)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int num[10], tmp[10], x[30], y[30], z[30], sz;
int ans;

void init(){
    sz = 0;
    for(int i = 2; i <= 9; i++){
        for(int j = i + 1; i + j <= 9; j++){
            x[sz] = i;
            y[sz] = j;
            z[sz++] = i + j;
        }
    }
    for(int i = 1; i <= 4; i++){
        x[sz] = i;
        y[sz] = i;
        z[sz++] = 2 * i;
    }
}

bool judge(int a[], int x, int y, int z, int t){
    if(x == y)
        return a[x] >= 2 * t && a[z] >= t;
    return a[x] >= t && a[y] >= t && a[z] >= t;
}

int cal(){
    for(int i = 1; i <= 9; i++) tmp[i] = num[i];
    int ans = 0;
    for(int i = 2; i < 9 && tmp[1]; i++){
        int t = min(2, min(tmp[1], min(tmp[i], tmp[i + 1])));
        if(t && judge(tmp, 1, i, i + 1, t)){
            tmp[1] -= t;
            tmp[i] -= t;
            tmp[i + 1] -= t;
            ans += t;
        }
    }
    return ans;
}

void dfs(int idx, int cnt){
    ans = max(ans, cnt + cal());
    if(idx == sz) return;
    dfs(idx + 1, cnt);
    int up = x[idx] != y[idx] ? 2 : 1;
    for(int i = 1; i <= up; i++){
        if(judge(num, x[idx], y[idx], z[idx], i)){
            num[x[idx]] -= i;
            num[y[idx]] -= i;
            num[z[idx]] -= i;
            dfs(idx + 1, cnt + i);
            num[x[idx]] += i;
            num[y[idx]] += i;
            num[z[idx]] += i;
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; cas++){
        for(int i = 1; i <= 9; i++){
            scanf("%d", &num[i]);
        }
        ans = 0;
        dfs(0, 0);
        printf("Case #%d: %d\n", cas, ans);
    }
    return 0;
}
/*
5
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
0 3 3 0 3 0 0 0 0
100 100 100 100 100 100 100 100 1
100 100 100 100 100 100 100 100 100

10
16 15 14 13 12 11 10 9 8
15 15 14 13 12 11 10 9 8
16 14 14 13 12 11 10 9 8
16 15 13 13 12 11 10 9 8
16 15 14 12 12 11 10 9 8
16 15 14 13 11 11 10 9 8
16 15 14 13 12 10 10 9 8
16 15 14 13 12 11 9 9 8
16 15 14 13 12 11 10 8 8
16 15 14 13 12 11 10 9 7

1
15 14 13 12 11 10 9 8 7

1
15 15 14 13 12 11 10 9 8
*/

100

101

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int num[10], tmp[10], x[30], y[30], z[30], sz;

int ans;

void init(){

sz = 0;

for(int i = 2; i <= 9; i++){

for(int j = i + 1; i + j <= 9; j++){

x[sz] = i;

y[sz] = j;

z[sz++] = i + j;

}

for(int i = 1; i <= 4; i++){

x[sz] = i;

y[sz] = i;

z[sz++] = 2 * i;

}

bool judge(int a[], int x, int y, int z, int t){

if(x == y)

return a[x] >= 2 * t && a[z] >= t;

return a[x] >= t && a[y] >= t && a[z] >= t;

}

int cal(){

for(int i = 1; i <= 9; i++) tmp[i] = num[i];

int ans = 0;

for(int i = 2; i < 9 && tmp[1]; i++){

int t = min(2, min(tmp[1], min(tmp[i], tmp[i + 1])));

if(t && judge(tmp, 1, i, i + 1, t)){

tmp[1] -= t;

tmp[i] -= t;

tmp[i + 1] -= t;

ans += t;

}

return ans;

}

void dfs(int idx, int cnt){

ans = max(ans, cnt + cal());

if(idx == sz) return;

dfs(idx + 1, cnt);

int up = x[idx] != y[idx] ? 2 : 1;

for(int i = 1; i <= up; i++){

if(judge(num, x[idx], y[idx], z[idx], i)){

num[x[idx]] -= i;

num[y[idx]] -= i;

num[z[idx]] -= i;

dfs(idx + 1, cnt + i);

num[x[idx]] += i;

num[y[idx]] += i;

num[z[idx]] += i;

}

int main(){

init();

int T;

scanf("%d", &T);

for(int cas = 1; cas <= T; cas++){

for(int i = 1; i <= 9; i++){

scanf("%d", &num[i]);

}

ans = 0;

dfs(0, 0);

printf("Case #%d: %d\n", cas, ans);

}

return 0;

}

1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2

0 3 3 0 3 0 0 0 0

100 100 100 100 100 100 100 100 1

100 100 100 100 100 100 100 100 100

16 15 14 13 12 11 10 9 8

15 15 14 13 12 11 10 9 8

16 14 14 13 12 11 10 9 8

16 15 13 13 12 11 10 9 8

16 15 14 12 12 11 10 9 8

16 15 14 13 11 11 10 9 8

16 15 14 13 12 10 10 9 8

16 15 14 13 12 11 9 9 8

16 15 14 13 12 11 10 8 8

16 15 14 13 12 11 10 9 7

15 14 13 12 11 10 9 8 7

15 15 14 13 12 11 10 9 8

HDU 5937 Equation (搜索,贪心)

LEAVE A COMMENT 取消回复