BOJ)1576 DNA점수

문제: icpc.me/1576

점수판을 채우는 규칙이 주어질 때 주어진 DNA 문자열의 각 문자열에서 얻을 수 있는 점수의 평균의 최댓값을 구하는 문제이다.

우리는 평균의 최댓값을 구하기 위해서 총점의 최댓값을 구하면 된다.

결국 총점이 최대가 되도록 점수판을 채우면 되는것이다.

우리는 다이나믹 프로그래밍을 이용해서 총점이 최대가 되도록 점수판을 채워나갈 것이다.

점수판을 채우는 순서는 임의로 지정해 줄 수 있다.

dp테이블은 dp[4][4][10*16*2] 이 될것이다.

dp 테이블이 의미하는 바는 dp[x][y][z]일때 (x,y)까지 채웠고 점수판의 점수 총합이 z일 때 총점의 최댓값으로 정의하면 된다.

우리는 점수판의 총점이 음수가 될 때도 있으니 그걸 고려하여 10*16의 총점에 2를 곱해주었다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#include <cstring>
#define INF 987654321
using namespace std;
int c[4][4], n, t, dp[4][4][10 * 16 * 2 + 10];
string a[101];
map<char, int> mp;
int func(int x, int y, int s) {
    if (x == 3 && y == -1) {
        if (s == 160)
            return 0;
        else
            return -INF;
    }
    if (x < y || x < 0 || y < 0)
        return -INF;
    if (s > 10 * 16 * 2 + 5 || s < 0)
        return -INF;
    int &ret = dp[x][y][s];
    if (ret != -1)return ret;
    ret = -INF;
    int tx, ty;
    if (x == y) {
        tx = 3;
        ty = y - 1;
    }
    else {
        tx = x - 1;
        ty = y;
    }
    if (x == y) {
        for (int i = 1; i <= 10; i++)
            ret = max(ret, func(tx, ty, s - i) + c[y][x] * i);
    }
    else {
        for (int i = -10; i <= 10; i++) {
            ret = max(ret, func(tx, ty, s - 2 * i) + c[y][x] * i);
        }
    }
    return ret;
}
int main() {
    mp['A'] = 0;
    mp['C'] = 1;
    mp['G'] = 2;
    mp['T'] = 3;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < a[i].length(); k++) {
                int x = mp[a[i][k]];
                int y = mp[a[j][k]];
                if (x > y)
                    swap(x, y);
                c[x][y]++;
            }
        }
    }
    memset(dp, -1, sizeof(dp));
    int r = func(3, 3, 160);
    double ans = (double)r / (n*(n - 1) / 2);
    printf("%.2lf\n", ans);
    return 0;
}