BYR Achieve · 镜像论坛

求大神帮做BUPT OJ 980. Zhuang Yi's Sister

2018/3/13镜像同步5 回复

求大神帮做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(); } } }

订阅后，新回复会通过你的通知中心匿名送达。