首页 > 代码库 > Gym 100917J---Judgement(01背包+bitset)
Gym 100917J---Judgement(01背包+bitset)
题目链接
http://codeforces.com/gym/100917/problem/J
Description
Statements
The jury of Berland regional olympiad in informatics does not trust to contest management systems, so the Berland regional programming contest is judged by the next way. There are n judges in the jury, each judge have authority ai. When jury receives a diskette with the new solution, each jury member reads its source and votes "OK" or "WA". If after the voting ends the sum of authorities of jury members, who think that solution is correct, is equal or greater to p, then soluton is accepted, otherwise it is rejected.
Several jury members think, that current system is too complicated for them and proposed some changes: each jury member will have new authority bi, and limit is changed to q; then, in their opinion, calculations will be easier, and nothing more changes.
You are hired by the Department of Education of Berland region to check if the new system is equivalent to old one, i.e. that at any possible distribution of votes final verdict with the new and with the old parameters will be the same. If the systems differ, output an example of voting, when verdicts in both systems are different.
Input
First line of the input contains one integer n (1 ≤ n ≤ 100) — number of judges in the jury.
Second line contains n + 1 integers p, a1, a2, ..., an (1 ≤ p, ai ≤ 106) — the current acception limit and the current values of authorities of jury members, respectively.
Third line contains n + 1 integers q, b1, b2, ..., bn (1 ≤ q, bi ≤ 106) — the new acception limit and the new values of authorities of jury members, respectively.
Output
If old and new systems are equivalent, print "YES". Otherwise in the first line of output print "NO", and in second print example of voting, with different verdicts in old and new systems. Voting is encoded with the string of length n, where i-th character is ‘1‘, if i-th judge considered solution correct and ‘0‘ otherwise.
If several answers are possible, print any of them.
Sample Input
3
8 4 5 6
2 1 1 1
YES
3
6 4 5 6
2 1 1 1
NO
001
题意：输入n表示有n个评委，现在有两种裁决方案：1、 p a[1]、a[2]......a[n] 表示每个评委的权值，如果第i个评委同意则总的评分加上a[i]，如果总分达到p则表示通过；
2、 q b[1]、b[2]......b[n] 与上面相同，如果总分达到q表示通过； 现在要求判断两种评选方案在任何情况下结果是否都是一样；
思路：定义mx[i]表示在第一种方案总分达到i（i<p）时，第二种方案能达到的最大得分，当在i<p&&mx[i]>=q时，则输出“NO” ，为了输出路径，可以使用bitset； 同样对调p和q a和b 再计算一次；
代码如下：
#include <iostream>#include <algorithm>#include <stdio.h>#include <cstring>#include <queue>#include <bitset>using namespace std;typedef long long LL;const int maxn=1e6+5;bitset<120>s[maxn];int a[105],b[105];int mx[maxn];int n;bool calc(int *a,int *b){ for(int i=0; i<maxn; i++) s[i].reset(); memset(mx,-1,sizeof(mx)); mx[0]=0; int top=0; for(int i=1; i<=n; i++) { for(int j=top; j>=0; j--) { if(mx[j]>-1) { if(j+a[i]<a[0]&&mx[j]+b[i]>mx[j+a[i]]) { mx[j+a[i]]=mx[j]+b[i]; s[j+a[i]]=s[j]; s[j+a[i]].set(i); top=max(top,j+a[i]); } if(j+a[i]<a[0]&&mx[j+a[i]]>=b[0])///一定要加上j+a[i]<a[0] 否则可能越界； { puts("NO"); for(int k=1; k<=n; k++) printf("%d",(int)s[j+a[i]][k]); puts(""); return true; } } } } return false;}int main(){ scanf("%d",&n); for(int i=0; i<=n; i++) scanf("%d",&a[i]); for(int i=0; i<=n; i++) scanf("%d",&b[i]); if(calc(a,b)) return 0; if(calc(b,a)) return 0; puts("YES"); return 0;}
Gym 100917J---Judgement(01背包+bitset)