分享到:文章主题: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
TianYing楼主
天樱道
等级
用户
文章
176
积分
2301
星座
天秤座
发信人: TianYing (天樱道), 信区: ACM_ICPC
标  题: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
发信站: 北邮人论坛 (Tue Mar 13 21:35:16 2018), 站内

求大神帮做BUPT OJ 980. Zhuang Yi's Sister
链接地址:http://10.105.242.83/problem/980/
我的WA答案:
import java.util.Scanner;
class E{
    int w;
    int v;
    int p;
}
public class Main {
    static int V1;
    static int V2;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int caseCout = 1;
        while(scanner.hasNext())
        {
            System.out.print("Case "+caseCout+": ");
            caseCout++;
            V1 = scanner.nextInt();
            V2 = scanner.nextInt();
            int n = scanner.nextInt();
            E[] listE = new E[n+1];
            int []mark = new int[n+1];
            for(int i=1;i<=n;i++)
            {
                mark[i] = 0;
            }
            int Ecount = 1;
            int T = n;
            while(T-- > 0)
            {
                int w = scanner.nextInt();
                int v = scanner.nextInt();
                int p = scanner.nextInt();
                E newE = new E();
                newE.w = w;
                newE.v = v;
                newE.p = p;
                listE[Ecount++] = newE;
            }
            int [][]dp1 = new int[n+1][V1+1];
            int [][]dp2 = new int[n+1][V2+1];
            for(int i=0;i<=V1;i++)
            {
                dp1[0][i] = 0;
            }
            for(int i=0;i<=V2;i++)
            {
                dp2[0][i] = 0;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=V1;j>=listE[i].w;j--)
                {
                    
                    if(dp1[i-1][j-listE[i].w]+listE[i].v > dp1[i-1][j])
                    {
                        mark[i] = 1;
                        dp1[i][j] = dp1[i-1][j-listE[i].w]+listE[i].v;
                        //System.out.println("物品i加入到bag1中"+i);
                    }
                    else{
                        dp1[i][j] = dp1[i-1][j];
                    }
                }
                if(V1 >= listE[i].w)
                for(int j=listE[i].w-1;j>=0;j--)
                {
                    //System.out.println( i + " "+j);
                    dp1[i][j] = dp1[i-1][j];
                }
                
                for(int j=V2;j>=listE[i].w;j--)
                {
                    if(mark[i] == 0)
                    {
                        if(dp2[i-1][j-listE[i].w]+listE[i].v > dp2[i-1][j])
                        {
                            mark[i] = 1;
                            dp2[i][j] = dp2[i-1][j-listE[i].w]+listE[i].v;
                            //System.out.println("物品i加入到bag2中"+i);
                        }
                        else{
                            dp2[i][j] = dp2[i-1][j];
                        }
                    }
                }
                if(V2 >= listE[i].w)
                for(int j=listE[i].w-1;j>=0;j--)
                {
                    dp2[i][j] = dp2[i-1][j];
                }
            }
            int eatMax = 0;
            int eatLoc = 0;
            boolean flag = false;
            int result = 0;
            for(int i=1;i<=n;i++)
            {
                //System.out.println(i+"-->"+mark[i]);
                if(mark[i] == 0 && listE[i].v > eatMax)
                {
                    eatMax = listE[i].v;
                    eatLoc = i;
                }
                if(listE[i].p == 1&&mark[i] == 0)
                {
                    eatMax = listE[i].v;
                    eatLoc = i;
                }
            }
            mark[eatLoc] = 1;
            for(int i=1;i<=n;i++)
            {
                //System.out.println(i+"-->"+mark[i]);
                if(listE[i].p == 1 && mark[i] == 0)
                {
                    flag = true;
                    break;
                }
                if(mark[i] == 1)
                    result += listE[i].v;
            }
            if(flag == true)
            {
                System.out.println(-1);
            }
            else System.out.println(result);
            System.out.println();
        }
    }
}


--

※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.128.241.*]
    返回顶部
    xcerwww沙发
    xcer
    等级
    版主
    文章
    359
    积分
    6355
    星座
    天蝎座
    发信人: xcerwww (xcer), 信区: ACM_ICPC
    标  题: Re: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
    发信站: 北邮人论坛 (Tue Mar 20 18:53:13 2018), 站内

    ema0
    --

    ※ 来源:·北邮人论坛手机客户端 bbs.byr.cn·[FROM: 114.242.249.*]
      返回顶部
      susliks板凳
      susliks
      等级
      用户
      文章
      32
      积分
      3458
      星座
      双鱼座
      发信人: susliks (susliks), 信区: ACM_ICPC
      标  题: Re: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
      发信站: 北邮人论坛 (Tue Mar 20 18:54:12 2018), 站内

      测试一下能不能用手机回复

      发自「贵邮」
      --

      ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 101.5.138.*]
        返回顶部
        susliks第3楼
        susliks
        等级
        用户
        文章
        32
        积分
        3458
        星座
        双鱼座
        发信人: susliks (susliks), 信区: ACM_ICPC
        标  题: Re: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
        发信站: 北邮人论坛 (Tue Mar 20 19:00:14 2018), 站内

        在校外上不了内网看不到题面,不过应该没什么变化,下次发帖可以考虑把题面放上来或者简单解释一下。

        给一个大致想法吧

        01背包变式:两个背包 + 有些必买物品 + 一次免费券

        dp[j][k][i]表示第一个背包装了j且第二个背包装了k且用了(1-i)张免费券后能得到的最大的开心值

        先算把特殊物品取了 在这个过程中得到三维dp数组的所有合法状态【如果特殊物品没取完 那么结果是dp数组的所有位置均为-1】
        然后再根据合法状态去取正常的物品

        算两个背包和枚举免费的物品这三个过程一定不能分开
        否则不能保证每件物品只取一次

        发自「贵邮」
        --

        ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 101.5.138.*]


        photo_1521543575_1.jpg
          返回顶部
          TianYing第4楼
          天樱道
          等级
          用户
          文章
          176
          积分
          2301
          星座
          天秤座
          发信人: TianYing (天樱道), 信区: ACM_ICPC
          标  题: Re: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
          发信站: 北邮人论坛 (Thu Mar 22 12:51:55 2018), 站内

          谢谢您,有没有网址看源码解析啊,我比较蠢,还是不懂
          【 在 susliks (susliks) 的大作中提到: 】
          : 在校外上不了内网看不到题面,不过应该没什么变化,下次发帖可以考虑把题面放上来或者简单解释一下。
          : 给一个大致想法吧
          : 01背包变式:两个背包 + 有些必买物品 + 一次免费券
          : ...................

          通过『我邮2.0』发布
          --

          ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.28.160.*]
            返回顶部
            susliks第5楼
            susliks
            等级
            用户
            文章
            32
            积分
            3458
            星座
            双鱼座
            发信人: susliks (susliks), 信区: ACM_ICPC
            标  题: Re: 求大神帮做BUPT OJ 980. Zhuang Yi's Sister
            发信站: 北邮人论坛 (Thu Mar 22 23:26:22 2018), 站内

            你是要准备研究生复试吧,或许可以另做一些简单一点的。我当时出这个题的时候定位是校赛预选赛的中高档难度,你确定要跟这个题死磕吗?

            【 在 TianYing 的大作中提到: 】
            : 谢谢您,有没有网址看源码解析啊,我比较蠢,还是不懂
            : 【 在 susliks (susliks) 的大作中提到: 】  
            : : 在校外上不了内网看不到题面,不过应该没什么变化,下次发帖可以考虑把题面
            : .........

            发自「贵邮」
            --

            ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 14.30.186.*]
              返回顶部
              • 文章数:6 分页:
                1. 1