HDU 1074 Doing Homework

正文索引 [隐藏]

题目翻译
题解
代码

传送门： http://acm.hdu.edu.cn/showproblem.php?pid=1074

题目翻译

有N个科目，每个科目有Deadline 和完成时间。每个科目每超过Deadline一天就会扣一分。
问如何安排，才能扣最少的分数。

题解

N很小只有15，所以我们想到状压DP，然后我们预处理出每种科目的组合完成所需要的时间finishedTime[now Subjects]
F[now Subjects + New Subject] = min (F[now Subjects + New Subject], max(F[now subjects] + finishedTime[now Subjects] + time[new subject] – deadline[new subject], 0))
记录方案很好实现

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int Maxn = 15;
int n;
struct SubjectNode
{
    char name[105];
    int time;
    int deadLine;
};
SubjectNode sbj[Maxn + 5];
int DP[(1<<15) + 5], pre[(1<<15) + 5];
int tim[(1<<15) + 5];
void dfsForOutput(int st){
    if (st == 0) return ;
    int subject = st ^ pre[st];
    dfsForOutput(pre[st]);
    for (int i = 0; i < n; i++)
        if ((1<<i) == subject)
        {
            printf("%s\n", sbj[i].name);
            return ;
        }
}
inline void solve(int T){
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s%d%d", sbj[i].name, &sbj[i].deadLine, &sbj[i].time);
    memset(DP, -1 ,sizeof(DP));
    memset(pre, 0, sizeof(pre));
    //memset(tim, 0, sizeof(tim));
    int lm = (1<<n) - 1;
    for (int st = 0; st <= lm; st++){
        tim[st] = 0;
        for (int i = 0; i < n; i++){
            if ((1<<i) & st) tim[st] += sbj[i].time;
        }
    }
    DP[0] = 0;
    for (int st = 0; st <= lm; st++){
        for (int i = 0; i < n; i++){
            if (((1<<i) & st) == 0)
            {
                int nxtST = st | (1<<i);
                if (DP[nxtST] == -1 || DP[nxtST] > DP[st] + max(0, tim[st] + sbj[i].time - sbj[i].deadLine))
                {
                    DP[nxtST] = DP[st] + max(0, tim[st] + sbj[i].time - sbj[i].deadLine);
                    pre[nxtST] = st;
                }
            }
        }
    }
    printf("%d\n", DP[lm]);
    dfsForOutput(lm);
}
int main()
{
    freopen("in.txt", "r", stdin);
    int T = 0;
    while(scanf("%d", &T) != EOF)
        for (int i = 1; i <= T; i++)
            solve(i);
    return 0;
}

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

const int Maxn = 15;

int n;

struct SubjectNode

{

char name[105];

int time;

int deadLine;

};

SubjectNode sbj[Maxn + 5];

int DP[(1<<15) + 5], pre[(1<<15) + 5];

int tim[(1<<15) + 5];

void dfsForOutput(int st){

if (st == 0) return ;

int subject = st ^ pre[st];

dfsForOutput(pre[st]);

for (int i = 0; i < n; i++)

if ((1<<i) == subject)

{

printf("%s\n", sbj[i].name);

return ;

}

inline void solve(int T){

scanf("%d", &n);

for (int i = 0; i < n; i++)

scanf("%s%d%d", sbj[i].name, &sbj[i].deadLine, &sbj[i].time);

memset(DP, -1 ,sizeof(DP));

memset(pre, 0, sizeof(pre));

//memset(tim, 0, sizeof(tim));

int lm = (1<<n) - 1;

for (int st = 0; st <= lm; st++){

tim[st] = 0;

for (int i = 0; i < n; i++){

if ((1<<i) & st) tim[st] += sbj[i].time;

}

DP[0] = 0;

for (int st = 0; st <= lm; st++){

for (int i = 0; i < n; i++){

if (((1<<i) & st) == 0)

{

int nxtST = st | (1<<i);

if (DP[nxtST] == -1 || DP[nxtST] > DP[st] + max(0, tim[st] + sbj[i].time - sbj[i].deadLine))

{

DP[nxtST] = DP[st] + max(0, tim[st] + sbj[i].time - sbj[i].deadLine);

pre[nxtST] = st;

}

printf("%d\n", DP[lm]);

dfsForOutput(lm);

}

int main()

{

freopen("in.txt", "r", stdin);

int T = 0;

while(scanf("%d", &T) != EOF)

for (int i = 1; i <= T; i++)

solve(i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑