hdoj 1074

Doing Homework

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11448    Accepted Submission(s): 5466

Problem Description

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.

 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework). 

Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.

 

Output

For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.

 

Sample Input

2

3

Computer 3 3

English 20 1

Math 3 2

3

Computer 3 3

English 6 3

Math 6 3

 

Sample Output

2

Computer

Math

English

3

Computer

English

Math

 

感觉所有的这之前做的所有dp我都想到贪心啊啊啊！！！qwq

我刚开始用及其单纯的方法，也有前面做到的一题的惯性思维，想着排序什么的去弄。

越弄越绕，用例对了，但是自己想的用例就不能过，感觉上就有很多逻辑错误，在这里记录一下自己的天真。（反正应该没有人看）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct subject{
    char name[106];
    int de,ne;
}s[20];

bool cmp( subject a, subject b)
{
    if(a.de==b.de&&a.ne>=a.de&&b.ne<=b.de)
        return a.ne<b.ne;
    else if( a.de==b.de&&a.ne<=a.de&&b.ne>=b.de)
        return a.ne<b.ne;
    return a.de<b.de;
}

int main()
{
    int T;
    while( ~scanf("%d",&T)){
        while(T--){
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                getchar();
                scanf("%s",s[i].name);
                scanf("%d%d",&s[i].de,&s[i].ne);
            }
            sort( s+1, s+1+n, cmp);

            int num=0,ti=0,ans=0,top=0,head=0,rem,tii;
            for(int i=1;i<=n;i++){
                 head+=s[i].ne;
                 top=s[i].de;
                 if(top<head){
                    num++; ti=top; rem=i; tii=0;
                    for(int j=top;j<=head;j++){
                        if((i+1)<=n&&s[i+1].de<j){
                            i++; head+=s[i].de;
                            num++;
                        }
                        printf("%s %d
",s[i].name,num);
                        if(tii>=s[rem].ne){
                            rem++; tii=0; num--;
                        }
                        tii++;
                        ans+=num;
                        if(num<=0) break;
                    }
                 }
            }

            printf("%d
",ans);
            for(int i=1;i<=n;i++){
                printf("%s
",s[i].name);
            }
        }
    }
    return 0;
}

就是排序，然后堆叠计算，然后直接输入排序后的结果。qwq

后面只能去搜了，唉！！！真的，什么时候凭借自己的想法做出来一波。qwq

用状压dp记录最优，代码很好理解。

代码来自：https://www.cnblogs.com/kuangbin/archive/2013/04/12/3016987.html

#include<cstdio>
using namespace std;
const int maxn=16;
const int inf=0x3f3f3f3f;
struct Node{
    char name[106];
    int d,c;
}node[maxn];
int dp[1<<maxn];
int pre[1<<maxn];
int n;

void output(int sta)
{
    if(sta==0) return ;
    int t=0;
    for(int i=0;i<n;i++){
        if((sta&(1<<i))!=0&&(pre[sta]&(1<<i))==0){
            t=i; break; ///当前物品有第i个，且下一个物品没有第i个的时候
        }
    }
    output(pre[sta]);
    printf("%s
",node[t].name);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s%d%d",node[i].name,&node[i].d,&node[i].c);
        }
        for(int i=0;i<(1<<n);i++)
            dp[i]=inf;
        dp[0]=0;
        for(int i=0;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if(i&(1<<j)) continue; ///在这个位置上面本来就有物品，跳过
                int s=0;
                for(int k=0;k<n;k++)
                    if(i&(1<<k)) s+=node[k].c; ///在该位置上面有物品就把消耗加进去
                s+=node[j].c;  ///该循环的作用主要体现在这里，要在i的基础上面把j的消耗加进去
                if(s>node[j].d) s=s-node[j].d;  ///消耗比截止的日期要大，就要相减
                else s=0; ///消耗少比截止日期小就为0即可。
                if(dp[i|(1<<j)]>dp[i]+s){
                    dp[i|(1<<j)]=dp[i]+s;
                    pre[i|(1<<j)]=i; ///更新前驱
                }
            }
        }
        printf("%d
",dp[(1<<n)-1]);
        output((1<<n)-1);
    }
    return 0;
}

理解代码后，自己敲了一遍。感觉理解得还行。