【SWTR-01】Sweet Round 01 T4 Doing Homework

Alex_Wei · 2019-10-03 00:42:34 · 题解

\color{#9400d3}\text{题面}

官方题解

我也不知道这个部分分给的有什么用

爆搜，期望得分 5-15\% （要看你怎么搜）

反正我也没写过爆搜

（大多数应该能拿到 100\%，除非被卡空间）

一看题就应该知道 时间 O(nk)，空间 O(k)

如果没有时间的限制，那么这道题目就是完全背包

但有了时间怎么办 qwq?

不慌，将所有种类的作业按时间从大到小排

每次一种作业去更新 dp 数组

再 对于每一个更新 求出最小（精力）花费

最后求出天数不就行了嘛 awa

记得用 long\ long 啊！

上代码

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3)
#define ll long long
ll read()//快读
{
    ll x=0,sign=1;char s=getchar();
    while(!isdigit(s))s=getchar();
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x;
}
const ll N=5e3+2;
const ll INF=1e18;

struct homew{
    ll x,w,t,cos; 
}k[N];
bool cmp(homew a,homew b){return a.t>b.t;}//将作业按时间大小排序

ll min(ll a,ll b){return a<b?a:b;}//手写 min 函数
ll x,w,n,dp[N<<1];

void init()
{
    x=read(),w=read(),n=read();
    for(int i=1;i<=n;i++)
        k[i].x=read(),k[i].w=read(),k[i].t=read();//读入
    sort(k+1,k+n+1,cmp);//sort 
    memset(dp,0x3f,sizeof(dp));//dp 赋初值
    dp[0]=0;
}

void DP()
{
    for(int i=1;i<=n;i++){
        if(k[i].w>=w)//特判一下 w[i]>=w 的情况
            dp[w]=min(dp[w],k[i].x);
        else
            for(int j=k[i].w;j<=w+k[i].w;j++)//完全背包
                dp[j]=min(dp[j],dp[j-k[i].w]+k[i].x);
        k[i].cos=INF;//赋初值
        for(int j=w;j<=(w<<1);j++)
            k[i].cos=min(k[i].cos,dp[j]);//找出最小值
    }
}

void answer()
{
    for(int i=n;i>0;i--){//时间从小到大遍历
        ll cos=k[i].cos*(k[i].t-k[i+1].t);//总花费
        if(cos<=x)x-=cos;//有足够的精力
        else cout<<k[i+1].t+x/k[i].cos<<" "<<x%k[i].cos<<endl,exit(0);//否则输出并退出
    }
    cout<<k[1].t<<" "<<x;//特判天天能写完作业
}

int main()
{
    init();
    DP();
    answer();
    return 0;
}