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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.