慕容琳的后花园
慕容琳的后花园
usaco#2018#February#Silver

T1-Rest Stops

题意是在一条长度为l的数轴上,有n个休息站,每个休息站有一个美味值,得到的美味单位为休息时间*美味值
有2个人速度分别为rF和rB,单位为秒每米,快的人不能在慢的人之后,求快的人能得到多少美味单位

解法

排序加贪心,我们易得一个结论,肯定是美味值大的休息站更优
可以把之前不是最优的累积到后面最优的处理,所以把休息站按照美味值从大到小排序,之后能取就取

ac代码

#include<bits/stdc++.h>
using namespace std;
struct p
{
    long long x,w;
}a[100010];
bool cmp(p aa,p bb)
{
    return aa.w>bb.w;
}
long long l,n,rf,rb,ans=0,nw=0;
int main()
{
    scanf("%lld%lld%lld%lld",&l,&n,&rf,&rb);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].x,&a[i].w);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].x<=nw)continue;
        ans+=(a[i].x-nw)*(rf-rb)*a[i].w;
        nw=a[i].x;
    }
    printf("%lld",ans);
    return 0;
}

T2-Snow Boots

给定一条路上有n块地砖,每块地砖有不同的积雪,有b双鞋子,每双鞋子有可承受的积雪以及最大步长
鞋子有顺序,他只能穿最上面的鞋子或丢掉最上面的鞋子,求他走到终点最少要丢掉几双鞋子

解法

这道题就是dp乱搞一下,设g[j]表示前i双鞋子能否走到j格,如果能走到就转移一下状态

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m,f[300],s[300],d[300],g[300];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&f[i]);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&s[i],&d[i]);
    g[1]=1;
    //初始化第一格
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<n;j++)
            if(g[j]&&f[j]<=s[i])
                for(int k=j+1;k<=min(n,j+d[i]);k++)
                    if(f[k]<=s[i])g[k]=1;
        if(g[n]){printf("%d",i-1);return 0;}
    }
}

T3-Teleportation

有n件物品要从ai搬运到bi,你可以设置一个起点为0的传送门,终点y是任意的,但是对于所有物品终点是一样的
求最小搬运距离和

解法

这道题我一开始也没想出来,我只推出来两种情况是abs(a-b)和abs(a)+abs(b-y)
收到某位同机房奆佬的点拨,设f(y)=min(abs(a-b),abs(a)+abs(b-y))
因为这个f(y)是一个具有分段线性的结构函数,我们就在求f(y)的时候遍历y,就可以了。每次当我们处理到两段函数的交界处时,我们就算出两个函数的斜率,算出其中的最小值
https://s2.ax1x.com/2019/03/02/kqYIiV.png
可以选择用map映射存储f(y)函数在各个交接点出的斜率的变化,然后再按照y的顺序遍历就可以得到答案了

ac代码

#include<bits/stdc++.h>
#define min(a,b) (a>b?b:a)
using namespace std;
long long n,a,b,x=0,y=-0x3f3f3f3f,s=0;
map<int,int>mp;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a,&b);
        x+=abs(a-b);
        if(abs(a)>abs(a-b))continue;
        mp[b]+=2;
        if((a<b&&a<0)||(a>=b&&a>=0))mp[0]--,mp[2*b]--;
        if((a<b&&a>=0)||(a>=b&&a<0))mp[2*b-2*a]--,mp[2*a]--;
    }
    long long ans=x;
    map<int,int>::iterator f;
    for (f=mp.begin();f!=mp.end();f++)
    {
        int yy=f->first,tmp=f->second;
        x+=s*(yy-y),y=yy,s+=tmp,ans=min(ans,x);
    }
    printf("%lld\n",ans);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

usaco#2018#February#Silver
T1-Rest Stops 题意是在一条长度为l的数轴上,有n个休息站,每个休息站有一个美味值,得到的美味单位为休息时间*美味值 有2个人速度分别为rF和rB,单位为秒每米,快的人不能在慢的人之后…
扫描二维码继续阅读
2019-05-06
功能