hdoj 1074 Doing Homework [상태 압축 dp]
제목: 15개의 임무를 제시하고 각 임무는 시간과 해야 할 일수가 있으며 기한을 넘기면 하루에 1점을 감점하여 감점을 최소화하는 안배 방안을 구한다.
분석: 상태 압축으로 모든 상태를 열거하고 dp[st]는 st상태에서의 최소 감점을 나타낸다
전이 방정식: dp[st | (1<이 문제는 인쇄 경로가 필요하기 때문에, 출력 결과를 되돌려 주는 그룹 저장 상태의 이동이 필요합니다.
AC
코드:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
const int N = 16;
int dp[1<<N];
struct Node
{
string s;
int time,cost;
};
Node a[N];
int pre[1<<N];
int n;
void Output(int status)
{
if(status==0)return;
int t=0;
for(int i=0;i<n;i++)
if( (status&(1<<i))!=0 && (pre[status]&(1<<i))==0 )
{
t=i;
break;
}
Output(pre[status]);
cout<<a[t].s<<endl;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>a[i].s>>a[i].time>>a[i].cost;
}
memset(dp,0x3f3f3f3f,sizeof(dp));
memset(pre,0,sizeof(pre));
dp[0]=0;
for(int st=0;st<(1<<n);st++)
{
//printf("**************************
");
int tmp=0;
for(int i=0;i<n;i++)
{
if(st&(1<<i))
tmp+=a[i].cost;
}
for(int i=0;i<n;i++)
{
//printf("fff %d %d %d",st,(1<<i),st&(1<<i));
if((st&(1<<i))==0)
{
if(dp[st|(1<<i)]>dp[st]+max(0,tmp+a[i].cost-a[i].time)){
dp[st|(1<<i)]=dp[st]+max(0,tmp+a[i].cost-a[i].time);
pre[st|(1<<i)]=st;
}
}
}
}
printf("%d
",dp[(1<<n)-1]);
Output((1<<n)-1);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.