[JSOI2014]结题报告+小结

[JSOI2014]宅男计划

三分+贪心，可以感性理解一下这个能宅的天数与叫外卖的次数为什么是一个单峰函数，如果叫外卖叫的少，那么费用就高，叫外卖叫的多，那么给外卖小哥的钱就很多，那么我们要使它们均衡，让能宅的天数达到峰值，三分一下叫外卖的次数

然后就是贪心，对于每一次叫外卖，按照食品的价格排个序，从便宜的开始，能选多少选多少

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int p,s;
}a[203];
int m,f,n,l,r,midl,midr;
int cmp(node nx,node ny)
{
    if(nx.p==ny.p)
        return nx.s>ny.s;
    return nx.p<ny.p;
}
int ask(int x)
{
    int sum=m-x*f,w=sum/x,las=sum-x*w,now=0,ans=0,loc=1,num;
    if(sum<=0)
        return 0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].s>=now&&a[i].p<=w)
            num=min(w/a[i].p,a[i].s-now+1),now+=num,w-=num*a[i].p;
        loc=i;
        if(a[i].p>w)
            break;      
    }
    ans=now*x,las+=w*x;
    for(int i=loc;i<=n;i++)
        if(a[i].s>=now&&a[i].p<=las)
            num=min(las/a[i].p,x),ans+=num,las-=num*a[i].p;
    return ans;
}
signed main()
{
    scanf("%lld%lld%lld",&m,&f,&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].p,&a[i].s);
    sort(a+1,a+n+1,cmp);
    l=1,r=m/f;
    while(l<r)
    {
        midl=(l+r)/2,midr=(l+r)/2+1;
        if(ask(midl)>=ask(midr))
            r=midl;
        else
            l=midr;
    }
    cout<<ask(l);
    return 0;
}

[JSOI2014]骑士游戏

这道题太巧妙了，我们先设\(f[i]\)表示消灭第\(i\)个怪兽所需要的最小体力，然后可以很显然的得出\(f[i]=min(k[i],s[i]+\sum_{j=1}^{r[i]}f[son[i][j]])\),看上去可以DP，但实际上并不行因为他可能有环，有后效性

然后，巧妙地点就在这里，可以发现这个式子有点像SPFA的松弛操作，于是我们先把所有的\(f[i]\)设为\(k[i]\)并入队,然后就可以进行松弛

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int rd()
{
    int p=1,x=0;
    char a=getchar();
    while((a<48||a>57)&&a!='-')
        a=getchar();
    if(a=='-')
        p=-p,a=getchar();
    while(a>47&&a<58)
        x=(x<<1)+(x<<3)+(a&15),a=getchar();
    return x*p;
}
int n,s[200003],k[200003],dis[200003],x,y,vis[200003],p,sum,ans;
vector<int>l[200003],g[200003];
queue<int>q;
signed main()
{
    n=rd();
    for(int i=1;i<=n;i++)
    {
        s[i]=rd(),k[i]=rd(),x=rd();
        for(int j=1;j<=x;j++)
            y=rd(),l[i].push_back(y),g[y].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        dis[i]=k[i];
        q.push(i),vis[i]=1;
    }
    while(!q.empty())
    {
        p=q.front(),q.pop(),vis[p]=0;
        sum=s[p];
        for(int j=0;j<l[p].size();j++)
            sum+=dis[l[p][j]];
        if(sum<dis[p])
        {
            dis[p]=sum;
            for(int j=0;j<g[p].size();j++)
                if(vis[g[p][j]]==0)
                    q.push(g[p][j]),vis[g[p][j]]=1;
        }
    }
    cout<<dis[1];
    return 0;
}

[JSOI2014]支线剧情2

很显然可以用树形DP

[JSOI2014]结题报告+小结

原文：https://www.cnblogs.com/dzice/p/12262996.html