题解

15 条题解

  • 8
    @ 2015-10-21 16:53:05

    很抱歉,那么迟才给大家带来题解。我也是蒟蒻,望大神觉得我有错或是怎么样不要太介意哈~

    为大家分析下题目。我们可以根据数据提示可以完全的猜出题目考察的范围。

    算法一:贪心,显然只能拿10-20分。不多提了。没人那么傻
    算法二:单纯DFS,大概能过30%的数据。
    算法三:根据题目信息进行DFS剪枝,50%的数据可以过

    算法四:动态规划。很容易设计出一个时间复杂度为N^3的动规。可以拿70分。也就是枚举每一列的每个点,然后再枚举前一行所有能到这个点的点进行动规。大家手上模拟模拟相信秒懂

    算法五(我自己乱想的),按题目信息建立有向图。然后spfa最短路。显然,建立图需要消耗的时间和算法四一样。但是这个思路更好理解。但是它还需要SPFA,因此可能会比算法4稍微超时。我是没试过。。

    算法六:优化的动态规划。显然这道题看最后的数据范围,n^2左右的算法才能满分。那么怎么在算法四的基础上少枚举一次??很简单。我们仔细模拟,发现他向上实质是完全背包,向下是01背包。因此只要循环2次即可,即枚举每一列的每个点即可。说专业点= =好像就是优化状态转移(其实我也听不懂233)。n(2*n)差不多。

    然后按这个思路动态规划。要注意顶端的特殊情况。第一次写我没考虑,结果就拿了75,后来研究了其他人的程序才猛然醒悟,切记,切记!!!

    那么我们很容易写出下面这个AC的程序

    ###pascal code
        program P1907;
        uses math;
        const maxn=100000001;
        var a,dp:array[-1..10000,0..1000] of longint;
            x,y:array[0..10000] of longint;
            k,m,p,l,h,i,j,ans,n,v:longint;
            ok:boolean;
            have:array[1..10000] of boolean;
        begin //main
        read(n,m,k); fillchar(a,sizeof(a),0); fillchar(dp,sizeof(dp),0); ans:=maxn;
        fillchar(have,sizeof(have),false);
        for i:=0 to n-1 do read(x[i],y[i]);
        for i:=1 to k do
        begin
         read(p,l,h); have[p]:=true;
         for j:=0 to l do a[p,j]:=maxn;
         for j:=h to m do a[p,j]:=maxn;
        end;
        for i:=0 to 1000 do a[-1,i]:=maxn;
        for i:=-1 to 10000 do a[i,0]:=maxn;
        
        for i:=-1 to 10000 do
         for j:=0 to 1000 do
          dp[i,j]:=maxn;
        
        for i:=0 to m do
         if a[0,i]<>maxn then
          dp[0,i]:=0;
        //以上是读入和初始化,注意游戏界面边缘的一些处理哦!
        for i:=1 to n do
        begin
         ok:=false; //记录是否还能继续游戏
         for j:=x[i-1]+1 to m do //向上飞的完全背包
          begin
           dp[i,j]:=min(dp[i,j],min(dp[i,j-x[i-1]]+1,dp[i-1,j-x[i-1]]+1));
           if dp[i,j]>maxn then
            dp[i,j]:=maxn;
          end;
        
         for j:=m downto m-x[i-1] do //顶部特判
          if a[i,m]<maxn then
           dp[i,m]:=min(min(dp[i,m],dp[i-1,j]+1),dp[i,j]+1);
        
         for j:=m-y[i-1] downto 1 do //向下掉
          if a[i,j]<maxn then
           dp[i,j]:=min(dp[i,j],dp[i-1,j+y[i-1]]);
        
         for j:=1 to m do //有水管的地方要改成无限大哦~
          if a[i,j]=maxn then
           dp[i,j]:=maxn;
        
         for j:=m downto 1 do
          if dp[i,j]<>maxn then
           ok:=true;
        
         if ok=false then begin v:=i; break; end; //已经无解了
        end;
        
        if ok=false then //无解的答案输出
        begin
         writeln('0'); ans:=0;
         for i:=1 to v-1 do
          if have[i]=true then
           inc(ans);
        
         writeln(ans);
         exit;
        end;
        
        for i:=m downto 1 do //计算有解时候的答案
        begin
         if dp[n,i]<ans then
          ans:=dp[n,i];
        end;
        
        writeln('1'); writeln(ans); //有解
        end.
    

    嗯,就是酱!

  • 3
    @ 2015-10-17 15:10:15

    #include <stdio.h>
    #include <limits.h>

    #define MIN(a,b) ((a)<(b)?(a):(b))

    int deltaP[10001]; //向上的位移
    int deltaN[10001]; //向下的位移
    int upperBound[10001]; //上界
    int lowerBound[10001]; //下界
    int hasPipe[10001]; //该处是否存在管道
    int dp[10001][1001]; //dp[i][j] = 到达 点(i,j) 的最小点击次数

    int main(){
    int width, height, numPipe;
    int i, j, coord, answer, flag, pipeCount = 0; //pipeCount存储至多可以通过多少管道

    scanf("%d %d %d", &width, &height, &numPipe);

    for(i=0; i<=width; i++){
    upperBound[i] = height+1; //注意:上界是开区间,即小鸟不能到达上界。
    lowerBound[i] = 0; //注意:下界是开区间,即小鸟不能到达下界。
    hasPipe[i] = 0;
    }
    for(i=1; i<=width; i++){
    for(j=1; j<=height; j++)
    dp[i][j] = LONG_MAX;
    }
    for(j=1; j<=height; j++)
    dp[0][j] = 0; //横坐标为零(在屏幕左端)时点击次数为0

    for(i=0; i<width; i++)
    scanf("%d %d", &deltaP[i], &deltaN[i]);
    for(i=0; i<numPipe; i++){
    scanf("%d", &coord); //管道坐标
    scanf("%d %d", &lowerBound[coord], &upperBound[coord]); //管道的处上下界
    hasPipe[coord] = 1; //标记此处有管道
    }

    for(i=0; i<width; i++){
    flag = 0;

    //在 点(i,j) 处点击一次屏幕造成的状态转移(即多重背包的初始化)
    for(j=lowerBound[i]+1; j<upperBound[i]; j++){
    coord = MIN(j+deltaP[i], height);
    if(dp[i][j] < LONG_MAX)
    dp[i+1][coord] = MIN(dp[i+1][coord], dp[i][j]+1);
    }

    //多重背包
    for(j=lowerBound[i]+1+deltaP[i]; j<=height; j++){
    coord = MIN(j+deltaP[i], height);
    if(dp[i+1][j] < LONG_MAX)
    dp[i+1][coord] = MIN(dp[i+1][coord], dp[i+1][j]+1);
    }

    //不点击屏幕造成的状态转移
    for(j=lowerBound[i]+1; j<upperBound[i]; j++){
    if(dp[i][j] == LONG_MAX)
    continue;
    else
    flag = 1; //若有横坐标为 i 时有可行解,则把flag置为 1,算法继续
    coord = j-deltaN[i];
    if(coord > 0)
    dp[i+1][coord] = MIN(dp[i+1][coord], dp[i][j]);
    }

    if(flag){
    if(hasPipe[i])
    pipeCount++; //若此处有管道,计数+1
    }else{
    break; //flag=0,没有可行解,退出
    }
    }

    answer = dp[width][1];
    for(j=2; j<=height; j++)
    answer = MIN(answer, dp[width][j]);
    if(answer < LONG_MAX)
    printf("1\n%d\n", answer);
    else
    printf("0\n%d\n", pipeCount);

    return 0;
    }

  • 1
    @ 2015-09-12 23:00:41

    const maxint=1000000000;
    var n,m,k,i,j,p,l,h,max,min,flag:longint;
    low,high,rise,drop,tube:array[0..1000] of longint;
    f:array[0..1000,0..100] of longint;

    begin
    readln(n,m,k);
    for i:=1 to n do
    begin
    low[i]:=0;
    high[i]:=m+1;
    end;
    for i:=1 to n do
    readln(rise[i],drop[i]);
    for i:=1 to k do
    begin
    readln(p,l,h);
    tube[p]:=1;
    low[p]:=l;
    high[p]:=h;
    end;
    for i:=1 to n do
    for j:=0 to m do
    f[i,j]:=maxint;
    for i:=1 to n do
    begin
    for j:=low[i]+1 to high[i]-1 do
    begin
    if j=m then
    begin
    for k:=1 to m-1 do
    if f[i-1,k]+(j-k-1) div rise[i]+1<f[i,j] then
    f[i,j]:=f[i-1,k]+(j-k-1) div rise[i]+1;
    if f[i-1,j]+1<f[i,j] then
    f[i,j]:=f[i-1,j]+1;
    continue;
    end;
    if j+drop[i]<=m then
    f[i,j]:=f[i-1,j+drop[i]];
    for k:=1 to (j-1) div rise[i] do
    if f[i-1,j-k*rise[i]]+k<f[i,j] then
    f[i,j]:=f[i-1,j-k*rise[i]]+k;
    end;
    if tube[i]=1 then
    begin
    flag:=0;
    for j:=low[i]+1 to high[i]-1 do
    if f[i,j]<>maxint then
    flag:=1;
    if flag=0 then
    begin
    writeln(0);
    writeln(max);
    exit;
    end
    else
    inc(max);
    end;
    end;
    min:=maxlongint;
    for i:=1 to m do
    if f[n,i]<min then
    min:=f[n,i];
    writeln(1);
    writeln(min);
    end.
    蒟蒻的70分垃圾程序...
    f[i,j]表示到(i,j)点时的最少跳跃次数...
    应该很好理解...

  • 0
    @ 2017-08-07 19:49:15

    /*
    这道题状态转移方程谁都可以想到不难,细节比较多,一个是本回合选择上升便不能下降,其次是管道不按顺序给,最后是一个略微的优化,就是顶部向上会停留在顶部。优化主要要求把一次摁多次的情况优化,具体看代码
    */
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int X[15000],Y[15000],f[10005][1005],L[15000],H[15000],p,l,h;
    bool flag=0;
    int main()
    {
    //freopen("bird.in","r",stdin);
    //freopen("bird.out","w",stdout);
    int n,m,q,c;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
    for(int j=0;j<=m;j++)
    {
    f[i][j]=100000;
    }
    }
    for(int i=0;i<n;i++)
    {
    cin>>X[i]>>Y[i];
    }
    for(int i=0;i<=n;i++)
    {
    H[i]=m+1;
    }
    for(int i=1;i<=q;i++)
    {
    cin>>p>>l>>h;
    L[p]=l;
    H[p]=h;
    }
    c=0;
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=m;j++)
    {
    if(j-X[i-1]>0)
    {
    f[i][j]=min(f[i][j],f[i-1][j-X[i-1]]+1);
    f[i][j]=min(f[i][j],f[i][j-X[i-1]]+1);
    }
    if(j==m)
    {
    for(int k=j-X[i-1];k<=m;k++)
    {
    f[i][j] = min(f[i][j], f[i-1][k] + 1);
    f[i][j] = min(f[i][j], f[i][k] + 1);
    }
    }
    }
    for(int j=m;j>0;j--)
    {
    if(j+Y[i-1]<=m)
    f[i][j]=min(f[i][j],f[i-1][j+Y[i-1]]);
    }
    for(int j=1;j<=m;j++)
    {
    if(j<=L[i]||j>=H[i])
    f[i][j]=100005;
    }
    if(H[i]!=m+1||L[i]!=0)
    c++;
    for(int k=1;k<=m;k++)
    {
    flag=0;
    if(f[i][k]<100000)
    {
    flag=1;
    break;
    }
    }
    if(flag==0)
    break;
    }
    int o=100000;
    c=c-1;
    for(int j=1;j<=m;j++)
    {
    o=min(o,f[n][j]);
    }
    if(o<100000)
    {
    cout<<1<<endl;
    cout<<o<<endl;
    }
    else
    {
    cout<<0<<endl;
    cout<<c<<endl;
    }
    //system("pause");
    return 0;
    }

  • 0
    @ 2017-01-20 19:48:07

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define oo 1000000000
    using namespace std;

    int n,m,t,f[10001][1001];

    struct node1
    {
    int l,h,x,y;
    bool b;
    }a[10001];

    int main()
    {
    scanf("%d%d%d",&n,&m,&t);
    for (int i=0;i<n;i++)
    scanf("%d%d",&a[i].x,&a[i].y);
    for (int i=1;i<=n;i++)
    {
    a[i].l=1;
    a[i].h=m;
    a[i].b=0;
    }
    for (int i=1;i<=t;i++)
    {
    int p,l,h;
    scanf("%d%d%d",&p,&l,&h);
    a[p].l=++l;
    a[p].h=--h;
    a[p].b=1;
    }
    int ans=0;
    bool suc=1;
    memset(f,0,sizeof(f));
    for (int i=1;i<=n;i++)
    {
    for (int j=1;j<=m;j++)
    {
    f[i][j]=oo;
    if (j-a[i-1].x>=1)
    f[i][j]=min(f[i][j],min(f[i-1][j-a[i-1].x]+1,f[i][j-a[i-1].x]+1));
    }
    for (int j=m-a[i-1].x;j<=m;j++)
    f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
    for (int j=a[i].l;j<=a[i].h;j++)
    if (j+a[i-1].y<=m)
    f[i][j]=min(f[i][j],f[i-1][j+a[i-1].y]);
    for (int j=0;j<=a[i].l-1;j++)
    f[i][j]=oo;
    for (int j=a[i].h+1;j<=m;j++)
    f[i][j]=oo;
    bool over=1;
    for (int j=1;j<=m;j++)
    if (f[i][j]<oo)
    {
    over=0;
    break;
    }
    if (over==1)
    {
    printf("%d\n",0);
    printf("%d\n",ans);
    suc=0;
    break;
    }
    else if (a[i].b==1)
    ans++;
    }
    if (suc==1)
    {
    ans=oo;
    for (int i=1;i<=m;i++)
    ans=min(ans,f[n][i]);
    printf("%d\n",1);
    printf("%d\n",ans);
    }
    }

  • 0
    @ 2016-10-03 20:03:09

    不是很懂哪里有问题。。。有没有大神帮忙看看
    60分RE
    ```c++
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int LEN=10010,HEIGHT=1010;
    const int INF=0x7fff0000;
    int n,m,k;
    int X[LEN],Y[LEN];
    bool hasPipe[LEN];
    int L[LEN],H[LEN];
    int d[LEN][HEIGHT];
    int dp(int x,int y);
    inline int getMin(int a,int b,int c){return min((a>b?b:a),c);}
    int main(){
    //freopen("bird.in","r",stdin);
    //freopen("bird.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++) scanf("%d%d",X+i,Y+i);
    for(int i=0;i<k;i++){
    int p;scanf("%d",&p);
    scanf("%d%d",L+p,H+p);
    hasPipe[p]=true;
    }
    int ans=INF;
    for(int i=1;i<=m;i++) ans=min(ans,dp(n,i));
    if(ans<INF){
    printf("%d\n%d",1,ans);
    }else{
    for(int i=n;i>=0;i--)
    for(int j=1;j<=m;j++)
    if(dp(i,j)<INF){
    int cnt=0;
    //cout<<"ans:"<<ans<<endl;
    for(int x=0;x<=i;x++) cnt+=hasPipe[i];
    printf("%d\n%d",0,cnt);
    return 0;
    }
    }
    return 0;
    }
    int dp(int x,int y){
    //printf("%d %d\n",x,y);
    if(d[x][y]) return d[x][y];
    if(hasPipe[x] && (y<=L[x] || y>=H[x])) return d[x][y]=INF;
    if(y<=0 || y>m) return d[x][y]=INF;
    if(x==0) return 0;
    else{
    if(y<m) return d[x][y]=getMin(dp(x,y-X[x-1])+1, dp(x-1,y-X[x-1])+1, dp(x-1,y+Y[x-1]));
    int ans=INF;
    for(int i=1;i<=X[x-1];i++)
    ans=min(ans,getMin(dp(x,y-i)+1, dp(x-1,y-i)+1, dp(x-1,y+Y[x-1])));
    return d[x][y]=ans;
    }
    }

  • 0
    @ 2016-08-13 10:10:27

    这道题用刷表法写思路要清晰一些,不过我写得有点丑

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int INF = 1000000000;
    const int maxn = 10000 + 10;
    const int maxm = 1000 + 10;
    int n, m, k;
    int X[maxn];
    int Y[maxn];
    int d[maxn][2];
    int pipe[maxn][2];
    
    void update (int a, int& b) {
        if (b < 0 || a < b) b = a;
    }
    
    void init () {
        cin >> n >> m >> k;
        for (int i = 0; i < n; i++) pipe[i][1] = m+1;
        for (int i = 0; i < n; i++) scanf("%d%d", &X[i], &Y[i]);
        
        for (int i = 0; i < k; i++) {
            int p, l, h; scanf("%d%d%d", &p, &l, &h);
            pipe[p][0] = l; pipe[p][1] = h;
        }
    }
    
    int main ()
    {
    //  freopen("in.txt", "r", stdin);
        init();
        int cnt = 0;
        int game_over = 0;
        
        int t = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= pipe[i][0]; j++) d[j][t] = -1;
            for (int j = pipe[i][1]; j <= m+1; j++) d[j][t] = -1;
            for (int j = 0; j <= m; j++) d[j][t^1] = -1;
            
            game_over = 1;
            for (int j = pipe[i][0]+1; j < pipe[i][1]; j++) 
                if (d[j][t] >= 0) { game_over = 0; break;}
            if (game_over) { cout << "0\n" << cnt; return 0;}
            
            if(pipe[i][1] < m+1) cnt++;
            
            for (int j = 1; j <= m; j++) if (d[j][t] >= 0)
                if (j > Y[i]) update(d[j][t], d[j-Y[i]][t^1]);
                
            for (int j = 1; j <= m; j++) if (d[j][t] >= 0)
                update(d[j][t]+1, d[min(m, j+X[i])][t]);
                
            for (int j = 1; j <= m; j++) if (d[j][t] >= 0)
                update(d[j][t]+1, d[min(m, j+X[i])][t^1]);
            
            t ^= 1;
        }
        int ans = INF;
        for (int i = 1; i <= m; i++) if (d[i][t] >= 0) ans = min(ans, d[i][t]);
        cout << "1\n" << ans;
        return 0;
    }
    
  • 0
    @ 2015-11-06 11:21:56

    记录信息
    评测状态 Accepted
    题目 P1907 飞扬的小鸟
    递交时间 2015-09-11 22:44:14
    代码语言 C++
    评测机 VijosEx
    消耗时间 157 ms
    消耗内存 664 KiB
    评测时间 2015-09-11 22:44:15
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 664 KiB, score = 5
    测试数据 #3: Accepted, time = 15 ms, mem = 664 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #5: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 664 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #8: Accepted, time = 20 ms, mem = 664 KiB, score = 5
    测试数据 #9: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #10: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #11: Accepted, time = 2 ms, mem = 660 KiB, score = 5
    测试数据 #12: Accepted, time = 0 ms, mem = 660 KiB, score = 5
    测试数据 #13: Accepted, time = 15 ms, mem = 664 KiB, score = 5
    测试数据 #14: Accepted, time = 1 ms, mem = 660 KiB, score = 5
    测试数据 #15: Accepted, time = 15 ms, mem = 660 KiB, score = 5
    测试数据 #16: Accepted, time = 15 ms, mem = 664 KiB, score = 5
    测试数据 #17: Accepted, time = 15 ms, mem = 660 KiB, score = 5
    测试数据 #18: Accepted, time = 28 ms, mem = 664 KiB, score = 5
    测试数据 #19: Accepted, time = 31 ms, mem = 660 KiB, score = 5
    Accepted, time = 157 ms, mem = 664 KiB, score = 100
    代码
    #include <cstdio>
    #include <cstring>

    const int MAXN = 10005;
    const int MAXM = 1005;
    const int INF = 0x3f3f3f3f;

    int n, m;
    int X[MAXN];
    int Y[MAXN];
    bool pipe[MAXN];
    int low[MAXN];
    int high[MAXN];
    int f[MAXM];
    int g[MAXM];

    void init()
    {
    int k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++i)
    scanf("%d%d", &X[i], &Y[i]);
    memset(pipe, 0, sizeof(pipe));
    for (int i = 0; i < k; ++i)
    {
    int p, l, h;
    scanf("%d%d%d", &p, &l, &h);
    --p;
    pipe[p] = true;
    low[p] = l;
    high[p] = h;
    }
    }

    bool fail_all()
    {
    for (int i = 1; i <= m; ++i)
    if (f[i] < INF) return false;
    return true;
    }

    void solve()
    {
    for (int i = 1; i <= m; ++i) f[i] = 0;
    for (int i = 0, count_pipe = 0; i < n; ++i)
    {
    int totmin = INF;
    for (int j = 1; j <= X[i]; ++j)
    {
    int min = INF;
    for (int k = j; k <= m; k += X[i])
    {
    g[k] = min;
    if (f[k] < min) min = f[k];
    ++min;
    }
    if (min < totmin) totmin = min;
    }
    if (totmin < g[m]) g[m] = totmin;
    for (int j = Y[i] + 1; j <= m; ++j)
    if (f[j] < g[j - Y[i]])
    g[j - Y[i]] = f[j];
    memcpy(f, g, sizeof(f));
    if (pipe[i])
    {
    for (int j = 1; j <= m; ++j)
    if (!(low[i] < j && j < high[i]))
    f[j] = INF;
    if (fail_all())
    {
    printf("0\n%d\n", count_pipe);
    return;
    }
    ++count_pipe;
    }
    }
    int min = INF;
    for (int j = 1; j <= m; ++j)
    if (f[j] < min) min = f[j];
    printf("1\n%d\n", min);
    }

    int main()
    {
    init();
    solve();

    fclose(stdin); fclose(stdout);
    return 0;
    }

  • 0
    @ 2015-10-24 17:50:16

    70分
    用了楼下的顶部特判毫无效果
    呵呵,我怎么感觉nm比nm2更好想呢
    1个点1个点好麻烦啊
    代码如下
    话说我的代码对的基本都是<3ms,而楼下都是100ms+
    var
    a,b:array[-200..10000,-200..1000]of longint;
    f:array[-200..10000,-200..1000]of boolean;
    c:array[0..10000]of boolean;
    x,y,l,h:array[0..10000]of longint;
    n,m,k,i,j,ans:longint;flag:boolean;
    function min(a,b:longint):longint;
    begin if a<b then exit(a);exit(b);end;
    procedure find(x:longint);
    var i,t:longint;
    begin t:=0;
    for i:=1 to x-1 do if c[i] then inc(t);
    writeln(0);writeln(t);halt;
    end;
    begin
    readln(n,m,k);
    for i:=1 to n do read(x[i],y[i]);
    for i:=1 to n do h[i]:=m;
    for i:=1 to n do l[i]:=1;
    for i:=1 to k do begin read(j);c[j]:=true;
    read(l[j]);inc(l[j]);read(h[j]);dec(h[j]);end;
    for i:=1 to m do f[0,i]:=true;
    for i:=1 to n do for j:=1 to m do b[i,j]:=1000000000;
    for i:=1 to n do begin flag:=false;
    if not c[i] then for j:=m downto 1 do if f[i-1,j] then
    begin f[i,m]:=true;b[i,m]:=min(b[i,m],b[i-1,j]+abs(m-j-1)div x[i]+1);
    flag:=true;end;
    for j:=l[i] to h[i] do if f[i-1,j-x[i]]or f[i,j-x[i]]
    then begin f[i,j]:=true;
    b[i,j]:=min(b[i,j],min(b[i,j-x[i]],b[i-1,j-x[i]])+1);
    flag:=true;end;
    for j:=l[i] to h[i] do if f[i-1,j+y[i]]
    then begin f[i,j]:=true;b[i,j]:=min(b[i,j],b[i-1,j+y[i]]);
    flag:=true;end;
    if not flag then find(i);end;
    ans:=maxlongint;
    for i:=1 to m do if (f[n,i])and(b[n,i]<ans) then ans:=b[n,i];
    writeln(1);writeln(ans);
    end.

    • @ 2015-10-24 20:09:56

      其实我代码100MS全是前面初始化的锅、只是稳点,其实我自己去掉过= =然后就0ms了

    • @ 2015-10-24 20:13:27

      你70分的点跟我没顶部特判错的点不一样。肯定不是顶部的关系

      你看看你DP边界有没有问题??

    • @ 2015-10-24 20:20:10

      好吧。确实我有些循环浪费了= =因为当时写的时候觉得能A就行了,没考虑太多优化。

      我当时没加顶部判断错的点是10 13 16.但是你的70分里都是对的。既然顶部判断没错用了我的顶部判断当然没任何ruan用。

      你把程序每次DP然后输出矩阵试试,看看能不能找出错。我当时也是这么排掉了。我估计要么就是边界要么就是你某个DP方程有点问题。

    • @ 2015-10-24 20:34:09

      好吧= =我了半个小时改不出你的程序。风格有点不习惯。。。抱歉了

    • @ 2015-10-25 09:18:44

      其实你的风格我也很不习惯
      不过可读性比我好多了
      大神哪个省的

    • @ 2015-10-25 09:20:46

      大神能花半个小时改蒟蒻的程序
      蒟蒻不胜感激

    • @ 2015-10-25 10:25:32

      加了个特判变成了85分
      不想搞了
      学校不行,基本没有时间搞竞赛,我还要看算法呢

    • @ 2015-10-25 18:29:13

      什么大神啊= =浙江省今年去当炮灰的.....

      你思路差不多是对的。我觉得吧。与其改你这程序还不如重做。。有的时候确实改不出来。。
      没有时间还能做成这样很不错了。你是那个省的?

    • @ 2015-10-25 19:21:53

      我差点以为是同一个人在自言自语

    • @ 2015-10-30 20:18:46

      膜拜楼上两位大神。。orz....

    • @ 2015-10-31 07:41:50

      蒟蒻来自山东。圈圈爷orz

    • @ 2015-11-01 20:28:39

      不对啊好像头像显示有问题 (。 怎么都一样

    • @ 2015-11-04 10:23:19

      蒟蒻从不用紫名2333

  • 0
    @ 2015-10-20 15:56:18

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define INF 1000000000
    #define MAXN 10000 + 10
    using namespace std;

    int u[MAXN], d[MAXN], map[MAXN][1000 + 10], f[MAXN][1000 + 10], bri[MAXN], m_d[MAXN], m_u[MAXN];

    int main()
    {
    int n, m, k, ans = 0;
    scanf("%d%d%d", &n, &m, &k);
    for(int i=0; i<n; i++)
    scanf("%d%d", &u[i], &d[i]);
    for(int i=1; i<=n; i++)
    m_d[i] = 1, m_u[i] = m;
    for(int i=1; i<=k; i++){
    int p, l, h;
    scanf("%d%d%d", &p, &l, &h);
    m_d[p] = l+1;
    m_u[p] = h-1;
    bri[i] = p;
    }
    for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
    f[i][j] = INF;
    if(j > u[i-1])
    f[i][j] = min(f[i][j], min(f[i-1][j-u[i-1]], f[i][j-u[i-1]])+1);
    }
    for(int j=m-u[i-1]; j<=m; j++)
    f[i][m] = min(f[i][m], min(f[i-1][j], f[i][j])+1);
    for(int j=m_d[i]; j<=m_u[i]; j++)
    if(j+d[i-1] <= m)
    f[i][j] = min(f[i][j], f[i-1][j+d[i-1]]);
    for(int j=0; j<m_d[i]; j++)
    f[i][j] = INF;
    for(int j=m_u[i]+1; j<=m; j++)
    f[i][j] = INF;
    int flag = 1;
    for(int j=1; j<=m; j++)
    if(f[i][j] < INF){
    flag = 0;
    break;
    }
    if(flag){
    ans = i-1;
    break;
    }
    }
    if(ans){
    sort(&bri[1], &bri[1]+k);
    int re = 0;
    for(int i=1; i<=k; i++)
    if(ans >= bri[i])
    re++;
    else
    break;
    printf("0\n%d", re);
    }
    else{
    int re = f[n][1];
    for(int i=2; i<=m; i++)
    re = min(re, f[n][i]);
    printf("1\n%d", re);
    }
    return 0;
    }
    DP[i][j]表示到i,j位置的最小点击屏幕数量
    是一个完全背包,,,,当年考场上没看出来。。。。现在终于A了

  • 0
    @ 2015-08-11 15:03:23

    #include<iostream>
    #include<cstdio>
    #define inf 1000000000
    using namespace std;
    int n,m,x[10100],y[10100],up[10100],down[10100],f[10100][1100],k,h,l,p;//高m 宽n
    int main()
    {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++)
    up[i]=m+1,down[i]=0;
    for(int i=1;i<=k;i++){
    scanf("%d%d%d",&p,&l,&h);
    up[p]=h;down[p]=l;
    }
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    f[i][j]=inf;
    f[0][0]=inf;
    for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    if(j-x[i-1]>=0){
    f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1);
    f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);
    }
    if(j==m)
    for(int k=j-x[i-1];k<=m;k++){
    f[i][j]=min(f[i][j],f[i-1][k]+1);
    f[i][j]=min(f[i][j],f[i][k]+1);
    }
    }
    for(int j=down[i]+1;j<=up[i]-1;j++){
    if(j+y[i-1]<=m)
    f[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);
    }
    for(int j=1;j<=down[i];j++)
    f[i][j]=inf;
    for(int j=up[i];j<=m;j++)
    f[i][j]=inf;
    }
    int ans=inf,temp=k;
    for(int i=n;i>=1;i--){
    for(int j=down[i]+1;j<=up[i]-1;j++)
    if(f[i][j]<inf)
    ans=min(ans,f[i][j]);
    if(ans!=inf) break;
    if(up[i]<=m) temp--;
    }
    if(temp==k)
    printf("1\n%d",ans);
    if(temp<k)
    printf("0\n%d",temp);
    }

  • 0
    @ 2015-07-26 13:34:02

    用变态规划即可

  • 0
    @ 2014-11-29 02:07:57

    “请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。”

    将解结构表示为\(\phi=(b,h,t)\),b为1或0表示是否可以完成游戏,若可以,h表示最少点击屏幕数;否则,t表示最多可以通过多少个管道缝隙。定义\(\phi_1=(b_1,h_1,t_1)<\phi_2=(b_2,h_2,t_2)\)当且仅当\((b_1=0,b_2=1\))\((b_1=b_2=0,t_1<t_2\))\((b_1=b_2=1,h_1>h_2\)),则我们可以对解的表示创建全序关系,而可行解的最大值为最优解,我们可以用有符号数来优化其内存表示。

    定义\(\phi+t'=\left\{\begin{array}{lr}
    (b,h,t+t') & b=0\\
    (b,h,t) & b=1
    \end{array}\right.\)
    \(\phi+h'=\left\{\begin{array}{lr}
    (b,h,t) & b=0\\
    (b,h+h',t) & b=1
    \end{array}\right.\)

    \(\phi(x,y)\)为从(x,y)坐标开始游戏的最优解,\(\alpha(x)\)\(\beta(x)\)分别表示上升与下降的高度,t(x)表示横坐标处是否存在管道,则对于不存在管道的平面区域$$
    \phi(x,y)=\max_{h=0,1,2,...}\left\{\begin{array}{lr}
    \phi(x+1,y+h*\alpha(x)) + h + t(x) & h>0 \\
    \phi(x+1,y-\beta(x)) + t(x) & h=0
    \end{array}\right.
    $$

    而所求解为\(\max_{1\le y\le m}\{\phi(0,y)\}\)。观察到表达式具有最优子结构性质,因此可以使用动态规划进行求解,时间复杂度为\(O(n*m^2)\)

    我们可以将每次可以不点击或点击多次,变为每次可以不点击、点击\(h_0\)次或原地上升一次,其中\(h_0\)为点击进入下一横坐标非管道区域的最小次数。从而可以进行下述优化,设\(\phi(x,y,\gamma)\)表示(x,y)坐标开始游戏的最优解,\(\gamma=0\)表示第一步不能为原地上升,而\(\gamma=1\)表示第一步可以为原地上升,则$$
    \phi(x,y,0)=\max\left\{\begin{array}{l}
    \phi(x+1,y+h_0*\alpha(x),1) + h(1) + t(x) \\
    \phi(x+1,y-\beta(x),0) + t(x)
    \end{array}\right.
    $$$$
    \phi(x,y,1)=\max\left\{\begin{array}{lr}
    \phi(x+1,y+h_0*\alpha(x),1) + h(1) + t(x) \\
    \phi(x+1,y-\beta(x),0) + t(x) \\
    \phi(x,y+\alpha(x-1),1) + h(1) + t(x) & x\neq 0
    \end{array}\right.
    $$

    从而得到\(O(n*m)\)的算法,空间复杂度可以实现为\(O(n+m)\)

    • @ 2014-12-31 23:37:04

      感觉好难懂……能不能稍微简单解释一下什么的……

  • 1

信息

ID
1907
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
3489
已通过
654
通过率
19%
被复制
7
上传者