HDU-4341 Gold miner 패키지 그룹화

6911 단어 HDU
여기에 여러 개의 점과 원점의 연결선이 공통되어 있다면 그것을 합쳐서 앞의 것을 단독으로 하고 앞의 두 개를 단독으로 해야 한다.마지막으로 바로 배낭을 나누면 됩니다.
코드는 다음과 같습니다.
#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAXN 205

using namespace std;



int N, M, cnt[MAXN], vis[MAXN], idx;



int f[40005];



struct Node

{

    int x, y, t, v;

    bool operator < (Node temp) const

    {

        return y < temp.y;

    } //  y     ,              

}e[MAXN];



struct Team

{

    int t, v;

}p[MAXN][MAXN];



bool Inline(int a, int b)

{

    return e[a].x * e[b].y == e[a].y * e[b].x;

}



void init()

{

    int st = 0, sv = 0;

    idx = 0;

    memset(vis, 0, sizeof (vis));

    memset(cnt, 0, sizeof (cnt));

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

        if (!vis[i]) {

            vis[i] = 1;

            ++idx, ++cnt[idx];

            st = e[i].t, sv = e[i].v;

            p[idx][cnt[idx]].t = st;

            p[idx][cnt[idx]].v = sv;

            for (int j = 1; j <= N; ++j) {

                if (!vis[j] && Inline(i, j)) {

                    vis[j] = 1; 

                    ++cnt[idx];

                    st += e[j].t, sv += e[j].v;

                    p[idx][cnt[idx]].t = st;

                    p[idx][cnt[idx]].v = sv;

                }

            }

        }

    }

}



void solve()

{

    memset(f, 0, sizeof (f));

    for (int i = 1; i <= idx; ++i) { //

        for (int t = M; t >= 0; --t) { //

            for (int j = 1; j <= cnt[i]; ++j) {

                if (t >= p[i][j].t) {

                    f[t] = max(f[t], f[t-p[i][j].t] + p[i][j].v);

                }

            }

        }

    }

    printf("%d
", f[M]); } int main() { int ca = 0; while (scanf("%d %d", &N, &M) == 2) { for (int i = 1; i <= N; ++i) { scanf("%d %d %d %d", &e[i].x, &e[i].y, &e[i].t, &e[i].v); } sort(e+1, e+1+N); printf("Case %d: ", ++ca); init(); solve(); } return 0; }

좋은 웹페이지 즐겨찾기