洛谷P1941 飞扬的小鸟 [noip2014] 背包

时间：2024-11-16 09:06:43

正解:背包

解题报告:

话说好久没做背包的题了,都有些陌生了?这几天加强基础题目多刷点儿dp和背包趴qwq

其实这题是95...然后我下了我错的那个测试点,我答案是9874正解是9875...然后读入又特别多实在搞不下来...太难受了QAQ太恶心了QAQ

于是我就 打表然后美滋滋地A了 挣扎了一会儿之后不得不面向数据编程A了这题

昂大概港下思路趴?我觉得我的思路应该是没错的...毕竟过了95分应该还是没有大问题dei

就是两个背包,一个完全一个01

完全是在于因为我们可以往上跳很多次鸭,所以就从小往大地做f[i][j]=min(f[i-1][j-x[i-1]]+1,f[i][j-x[i-1]]+1)

然后01是往下降只能降一次,然后就f[i][j]=min(f[i][j],f[i-1][j+y[i-1]])

然后注意一下那个到顶上的事儿特殊处理下就成了

对了这题的话我们可以发现其实f[i][]只会从f[i-1][]和f[i][]转移来所以其实应该是可以开f[1/2/3][]就够了?(当开不下的时候

但是反正是开得下的而且那样很麻烦鸭,那就直接设就行了不用想那么多嘛qwq

over.放个代码我就去做NOIp2014最后一题辣!我真滴觉得我今天能搞完14年的!yeah!

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i)

+,M=+;
ll n,m,k,x[N],y[N],f[N][M],ans;
struct guandao{ll l,h;}gd[N];
;

inline ll read()
{
    ;;
    '))ch=getchar();
    if(ch=='-')ch=getchar();
    )+(x<<)+(ch^'),ch=getchar();
    return y?x:-x;
}
inline ll check(){;i--)rp(j,,m)][])return i;}

int main()
{
    n=read();m=read();k=read();memset(f,/,][];
    rp(i,,n)x[i]=read(),y[i]=read(),gd[i].l=,gd[i].h=m+;gd[n+].l=;gd[n+].h=m+;
    rp(i,,k){ll t=read()+;gd[t].l=read(),gd[t].h=read();}
    rp(i,gd[].l+,gd[].h-)f[][i]=;++n;
    rp(i,,n)
    {
        rp(j,x[i-]+,x[i-]+m)f[i][j]=min(f[i-][j-x[i-]]+,f[i][j-x[i-]]+);
        rp(j,m+,m+x[i-])f[i][m]=min(f[i][m],f[i][j]);
        rp(j,,m-y[i-])f[i][j]=min(f[i][j],f[i-][j+y[i-]]);
        rp(j,,gd[i].l)f[i][j]=f[][];rp(j,gd[i].h,m)f[i][j]=f[][];
    }
    rp(i,gd[n].l+,gd[n].h-)if(f[n][i])ans=min(f[n][i],ans);
    )++ans;
    ][]);
    ll cjk=check();
    ans=;
    rp(i,,cjk) || gd[i].h!=m+)++ans;
    printf("0\n%lld\n",ans);
    ;
}

95我也很绝望鸭QAQ

相关文章