首页 > 代码库 > zzuli1985（dp/水dfs郑轻比赛）

zzuli1985（dp/水dfs郑轻比赛）

2024-09-10 14:17:19   216人阅读

再一次感受到dp的威力

1985: 即将到来的新生赛

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 112  Solved: 28

SubmitStatusWeb Board

Description

新生赛马上就要到来了。为了举办这次比赛，学校也是大费苦心。由于时间紧迫，要准备的事情太多，人员安排也是很伤脑子。身为一个聪明的acmer，这点小事对你来说应该是So easy!
距离新生赛开始剩余100个小时，现在还剩余m项任务。每个任务都有开始时间，结束时间和收益。现在想知道怎么安排这些任务使人员安排的效率最大（收益最高）。
注：同一时间只能做一个任务， 一个任务结束后可以立马开始另外一个任务，也就是说下一个任务的开始时间可以等于正在做的任务的结束时间。由于有些任务是有时间上的冲突， 所以这些任务是选作，可以不用全部完成。

Input

输入第一行为整数T，表示有T组测试数据。
每组测试数据第一行为一个整数m，表示剩余任务。随后m行，每行三个整数b，e和v分别表示其中一项活动的开始时间，结束时间和收益。(0<=b < e<=100 ,0<=v<=10000,1<=m<=20)

Output

输出最高收益。

Sample Input

1 4 0 5 10 3 7 14 5 9 7 6 9 8

Sample Output

18 
比赛时肯定是一联萌币>_<；
寒假学了搜索后就写了个暴力dfs水过去了，因为数据实在太小了：
#include<iostream>
#include<cstring>
using namespace std;                                 //尝试所有可能的排列组合安排并更新最大价值
int b[21],e[21],v[21],m,maxn,book[21],sumn,ed; 
void dfs(int p)
{
    for (int i=1;i<=m;i++){
        if (p==0) sumn=0;
        if (!book[i]){
            if (b[i]>=e[p]){book[i]=1;
         
            sumn+=v[i];
             
            if (sumn>maxn) maxn=sumn;
             
            dfs(i);
            sumn-=v[i];
            book[i]=0;}
            }
         
    }
}
int main()
{
    int n,i,j,t;
    cin>>t;
    while (t--){maxn=-1;
        cin>>m;memset(book,0,sizeof(book));
    memset(e,0,sizeof(e));memset(b,0,sizeof(b));
        for (i=1;i<=m;i++)
        cin>>b[i]>>e[i]>>v[i];
        sumn=0,dfs(0);
        cout<<maxn<<endl;
    }
    return 0;
}
 
今天发现是个dp：
利用结构体储存下变量，按结束时间排序dp寻找最大价值
注意：
由于第i个事件可能与之前所有的都匹配失败，此时就应把之前最大的价值作为dp[i]的价值，
我这里没这样做，而是结束后扫描了一遍dp数组找到最大价值

#include<bits/stdc++.h>
using namespace std;
int dp[105];
struct tim
{
int s,e,w;
bool operator<(const tim &chs)const{
if(e!=chs.e) return e<chs.e;
else return s<chs.s;
}
};
int main()
{
int n,i,j,k,s,e,w,p,t;
cin>>t;
while(t--){tim m[30];
int maxn=-1;
memset(dp,0,sizeof(dp));
cin>>n;
m[0].e=0;
for(i=1;i<=n;++i)
cin>>m[i].s>>m[i].e>>m[i].w;
sort(m+1,m+1+n);
for(i=1;i<=n;++i){
int pd=0;
for(j=0;j<i;++j)
if(m[i].s>=m[j].e&&pd<dp[j]) pd=dp[j];
dp[i]=pd+m[i].w;
}
for(i=1;i<=n;++i) maxn=max(dp[i],maxn);
cout<<maxn<<endl;
}
return 0;
}

zzuli1985（dp/水dfs郑轻比赛）


联系
我们