HDU 1074 Doing Homework
【摘要】 题目链接~~>
做题感悟：这题以前看过但是没做出来，也不知道用状态压缩，今天做了一下竟然1A ，悲剧的是AC 之后我看别人都没排序，so~>自己也罢排序的删掉结果就wa了，这是为什么？？？
解题思路：状态压缩 + 记忆化搜索
dp[ S ] 代表达到...
做题感悟：这题以前看过但是没做出来，也不知道用状态压缩，今天做了一下竟然1A ，悲剧的是AC 之后我看别人都没排序，so~>自己也罢排序的删掉结果就wa了，这是为什么？？？
解题思路：状态压缩 + 记忆化搜索
dp[ S ] 代表达到状态 S 所减少的分数，其中S中的每一位代表某项作业到达状态 S 该作业已经做过。那么 dp[ S ] = min { dp [ S^(1<<i) ] + mx } ( 0 <= i < n ,mx 只加上i后减少的分数) ，还要开一个数组记录结束的天数，这里到达同一种状态所用的总天数是一样的。然后记忆化搜索就ok 了 。这里有一点不明白的是：问什么我不排序就wa，难道这靠人品吗
？？求指教？？
代码：
-
#include<iostream>
-
#include<sstream>
-
#include<map>
-
#include<cmath>
-
#include<fstream>
-
#include<vector>
-
#include<sstream>
-
#include<cstring>
-
#include<cstdio>
-
#include<stack>
-
#include<queue>
-
#include<bitset>
-
#include<ctime>
-
#include<string>
-
#include<iomanip>
-
#include<algorithm>
-
using namespace std ;
-
#define INT long long int
-
const int INF = 0x3f3f3f3f ;
-
const double esp = 0.00000001 ;
-
const double PI = acos(-1.0) ;
-
const int mod = 6 ;
-
const int MY = 8 ;
-
const int MX = 50000 + 5 ;
-
int n ;
-
int pre[MX] ;
-
int dp[MX] ,day[MX] ,pt[MX] ;
-
struct node
-
{
-
char s[105] ;
-
int x ,y ;
-
}T[MX] ;
-
bool cmp(node a ,node b)
-
{
-
return strcmp(a.s ,b.s) > 0 ;
-
}
-
void input()
-
{
-
scanf("%d" ,&n) ;
-
memset(dp ,-1 ,sizeof(dp)) ;
-
dp[0] = day[0] = pre[0] = 0 ;
-
for(int i = 0 ;i < n ; ++i)
-
{
-
scanf("%s%d%d" ,T[i].s ,&T[i].x ,&T[i].y) ;
-
pre[1<<i] =1<<i ;
-
}
-
sort(T ,T+n ,cmp) ; // 排序
-
}
-
int DP(int S) // 记忆化搜索
-
{
-
if(dp[S] != -1) return dp[S] ;
-
int& ans = dp[S] ;
-
ans = day[S] = INF ;
-
int temp ,d ,cost ,end ;
-
for(int i = 0 ;i < n ; ++i)
-
if((S&(1<<i)))
-
{
-
temp = DP(S^(1<<i)) ;
-
d = day[S^(1<<i)] ;
-
end = d + T[i].y ;
-
if(T[i].x <= d)
-
cost = d-T[i].x + T[i].y ;
-
else
-
{
-
if(T[i].x-d >= T[i].y)
-
cost = 0 ;
-
else
-
cost = T[i].y - T[i].x + d ;
-
}
-
if(ans > temp + cost)
-
{
-
ans = temp+cost ;
-
day[S] = end ;
-
pre[S] = S^(1<<i) ;
-
}
-
}
-
return ans ;
-
}
-
void print(int S) // 递归输出
-
{
-
if(pre[S] != S)
-
{
-
print(pre[S]) ;
-
cout<<T[pt[pre[S]^S]].s<<endl ;
-
}
-
else return ;
-
}
-
void init()
-
{
-
for(int i = 0 ;i < 15 ; ++i)
-
pt[1<<i] = i ;
-
}
-
int main()
-
{
-
init() ;
-
int Tx ;
-
scanf("%d" ,&Tx) ;
-
while(Tx--)
-
{
-
input() ;
-
cout<<DP((1<<n)-1)<<endl ;
-
print((1<<n)-1) ;
-
}
-
return 0 ;
-
}
-
-
解题思路：这题意思和上面一题差不多，改变了一点就可以用贪心解决。
方法一、对截至时间排序，如果时间相等则价值从大到小排。
需要用一个数记录已经写了几天了，因为时间是排好序的，如果处理到第 i 个，如果第 i 个的截至时间小于前面的累计时间那么记录天数加一就可以。如果第 i 个的截至时间大于等于前面累计的时间，就在前面找一个价值最小的且没被标记的任务标记，等于替换了最小的价值的任务，这样最终的结果为标记了的任务的价值。
方法二、对价值排序，如果价值相等时间从小到达排。
价值从大到小排序，如果当前处理第 i 个任务，则从当前任务的截至时间开始往前找，看那一天没有被标记过，如果没有找到就应该加到最终的结果中，尽量选择靠近截止时间的那天做当前作业。
代码（方法一）：
-
#include<iostream>
-
#include<sstream>
-
#include<map>
-
#include<cmath>
-
#include<fstream>
-
#include<vector>
-
#include<sstream>
-
#include<cstring>
-
#include<cstdio>
-
#include<stack>
-
#include<queue>
-
#include<bitset>
-
#include<ctime>
-
#include<string>
-
#include<iomanip>
-
#include<algorithm>
-
using namespace std ;
-
#define INT long long int
-
const int INF = 0x3f3f3f3f ;
-
const double esp = 0.00000001 ;
-
const double PI = acos(-1.0) ;
-
const int mod = 6 ;
-
const int MY = 8 ;
-
const int MX = 1000 + 5 ;
-
int n ;
-
bool vis[MX] ;
-
struct node
-
{
-
int x ,y ;
-
}T[MX] ;
-
bool cmp(node a ,node b)
-
{
-
if(a.x != b.x)
-
return a.x < b.x ;
-
else return a.y > b.y ;
-
}
-
void input()
-
{
-
scanf("%d" ,&n) ;
-
for(int i = 1 ;i <= n ; ++i)
-
scanf("%d" ,&T[i].x) ;
-
for(int i = 1 ;i <= n ; ++i)
-
scanf("%d" ,&T[i].y) ;
-
sort(T+1 ,T+n+1 ,cmp) ;
-
}
-
void solve()
-
{
-
memset(vis ,false ,sizeof(vis)) ;
-
int num = 0 ,ans = 0 ;
-
for(int i = 1 ;i <= n ; ++i)
-
{
-
-
if(num < T[i].x)
-
num++ ;
-
else
-
{
-
int flag = i ,Max = T[i].y ;
-
for(int j = 1 ;j < i ; ++j)
-
if(!vis[j] && T[j].y < Max) // 如果没被标记
-
{
-
Max = T[j].y ;
-
flag = j ;
-
}
-
if(flag == i)
-
{
-
vis[i] = true ;
-
ans += T[i].y ;
-
}
-
else
-
{
-
vis[flag] = true ;
-
ans += Max ;
-
}
-
}
-
}
-
cout<<ans<<endl ;
-
}
-
int main()
-
{
-
int Tx ;
-
scanf("%d" ,&Tx) ;
-
while(Tx--)
-
{
-
input() ;
-
solve() ;
-
}
-
return 0 ;
-
}
-
-
#include<iostream>
-
#include<sstream>
-
#include<map>
-
#include<cmath>
-
#include<fstream>
-
#include<vector>
-
#include<sstream>
-
#include<cstring>
-
#include<cstdio>
-
#include<stack>
-
#include<queue>
-
#include<bitset>
-
#include<ctime>
-
#include<string>
-
#include<iomanip>
-
#include<algorithm>
-
using namespace std ;
-
#define INT long long int
-
const int INF = 0x3f3f3f3f ;
-
const double esp = 0.00000001 ;
-
const double PI = acos(-1.0) ;
-
const int mod = 6 ;
-
const int MY = 8 ;
-
const int MX = 1000 + 5 ;
-
int n ;
-
bool vis[MX] ;
-
struct node
-
{
-
int x ,y ;
-
}T[MX] ;
-
bool cmp(node a ,node b)
-
{
-
if(a.y != b.y)
-
return a.y > b.y ;
-
else return a.x < b.x ;
-
}
-
void input()
-
{
-
scanf("%d" ,&n) ;
-
for(int i = 1 ;i <= n ; ++i)
-
scanf("%d" ,&T[i].x) ;
-
for(int i = 1 ;i <= n ; ++i)
-
scanf("%d" ,&T[i].y) ;
-
sort(T+1 ,T+n+1 ,cmp) ;
-
}
-
void solve()
-
{
-
int ans = 0 ;
-
memset(vis ,false ,sizeof(vis)) ;
-
for(int i = 1 ;i <= n ; ++i)
-
{
-
int j = T[i].x ;
-
for( ;j >= 1 ; --j)
-
if(!vis[j])
-
{
-
vis[j] = true ;
-
break ;
-
}
-
if(j == 0)
-
ans += T[i].y ;
-
}
-
cout<<ans<<endl ;
-
}
-
int main()
-
{
-
int Tx ;
-
scanf("%d" ,&Tx) ;
-
while(Tx--)
-
{
-
input() ;
-
solve() ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/39296501
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）