hdu 5045 Contest(dp)
제목의 대의: 한 팀에 N 명이 있고 경기는 모두 M 개의 문제가 있으며 하나의 행렬을 정해서 모든 사람이 상응하는 문제를 맞히는 정확도를 나타낸다.현재 매 문제에 대해 한 명의 학생을 파견하여 문제를 풀 수 있지만, 임의의 시간에 임의의 두 학생의 문제 수는 두 문제 이상 차이가 나면 안 된다.
문제풀이 사고방식: dp[i][s]는 i문제에서 s는 이진법 상태를 나타내고 어떤 사람이 문제를 풀었는지(상응하는 것)를 나타낸다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 15;
const int maxm = 2005;
const int maxs = (1<<10) + 5;
const double INF = 0x3f3f3f3f;
int N, M;
double p[maxn][maxm], dp[maxm][maxm];
void init () {
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 1; j <= M; j++)
scanf("%lf", &p[i][j]);
}
}
double solve () {
int T = 1<<N;
for (int i = 0; i <= M; i++)
for (int j = 0; j < T; j++)
dp[i][j] = -INF;
dp[0][0] = 0;
for (int i = 1; i <= M; i++) {
for (int s = 0; s < T; s++) {
for (int k = 0; k < N; k++) {
if (s & (1<<k))
continue;
dp[i][s | (1<<k)] = max(dp[i][s | (1<<k)], dp[i-1][s] + p[k][i]);
}
}
dp[i][0] = dp[i][T-1];
}
double ret = 0;
for (int i = 0; i < T; i++)
ret = max(ret, dp[M][i]);
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
init();
printf("Case #%d: %.5lf
", kcas, solve());
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
