{"id":237,"date":"2017-08-08T07:55:00","date_gmt":"2017-08-08T07:55:00","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=237"},"modified":"2017-08-05T08:18:09","modified_gmt":"2017-08-05T08:18:09","slug":"%e7%99%be%e5%ba%a6%e4%b9%8b%e6%98%9f2017-1004-%e5%ba%a6%e5%ba%a6%e7%86%8a%e7%9a%84%e5%8d%88%e9%a5%ad%e6%97%b6%e5%85%89-%e5%9b%9e%e6%ba%af","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=237","title":{"rendered":"\u767e\u5ea6\u4e4b\u661f2017 1004 \u5ea6\u5ea6\u718a\u7684\u5348\u996d\u65f6\u5149 \u56de\u6eaf"},"content":{"rendered":"

\u8fd9\u9053\u9898\u521a\u5f00\u59cb\u6837\u4f8b\u6539\u4e86\u597d\u591a\u6b21\uff0c\u641e\u5f97\u524d\u4e00\u4e2a\u5c0f\u65f6\u65e0\u4ece\u4e0b\u624b\u3002\u6298\u817e\u4e861002\u65e0\u679c\u4ee5\u540e\u8f6c1004\uff0c\u540e\u6765\u53d1\u73b0\u662f\u4e00\u4e2a\u7b80\u5355\u76840-1\u80cc\u5305\u95ee\u9898\uff0c\u552f\u4e00\u8981\u6ce8\u610f\u7684\u662f\u8bb0\u5f55\u8def\u5f84\uff0c\u5f53\u6709\u591a\u7ec4\u6700\u4f18\u89e3\u7684\u65f6\u5019\u9996\u5148\u53d6\u6700\u4f18\u89e3\u5e8f\u53f7\u548c\u6700\u5c0f\u7684\u4e00\u7ec4<\/strong>\uff0c\u7136\u540e\u662f\u53d6\u6700\u4f18\u89e3\u5e8f\u53f7\u6570\u7ec4\u6392\u5217\u5b57\u5178\u6811\u6700\u5c0f\u7684\u4e00\u7ec4<\/strong>\uff0c\u7b80\u5355\u641e\u641e\u5c31\u8fc7\u4e86\u3002
\n[cc lang=”c”]#include
\n#include
\n#define in(x) scanf(“%d”,&x)
\n#define inl(x) scanf(“%lld”,&x)
\n#define ins(x) scanf(“%s”,x)
\n#define inf(x) scanf(“%lf”,&x)
\n#define inc(x) scanf(“%c”,&x)
\n#define gc() getchar()
\n#define out(x) printf(“%d\\n”,x)
\n#define outl(x) printf(“%lld\\n”,x)
\n#define od(x, y) printf(“%d %d”,x,y)
\n#define ms(x) memset(x,0,sizeof(x))
\n#define msc(x, n) memset(x,n,sizeof(x))
\n#define cp(x) while(!x.empty())x.pop()
\n#define rep(i, a, b) for(int i=a;i<b;++i) #define rvep(i, a, b) for(int i=a;i>=b;–i)
\n#define elif else if
\n#define el else
\n#define wl(x) while(x)
\n#define sn scanf
\n#define bl bool
\n#define mp make_pair
\n#define pii pair<int,int>
\n#define rtn return
\n#define ope operator
\n#define cst const
\n#define it int
\n#define stt struct
\n#define il inline
\n#define db double
\n#define pf printf
\ntypedef long long ll;
\ntypedef void vt;
\nusing namespace std;
\ncst it INF = 0x3f3f3f3f;
\nint n, c, bestp, bestw;
\nint p[10000], w[10000], x[10000], bestx[10000];
\nint tmp1[10100], tmp2[10100];
\nvoid Backtrack(int i, int cp, int cw)
\n{
\nint j;
\nif (i > n)
\n{
\nif (cp > bestp)
\n{
\nbestp = cp;
\nbestw = cw;
\nfor (int l = 0; l <= n; l++) bestx[l] = x[l];
\n}
\nelse if (cp == bestp)
\n{
\nms(tmp1), ms(tmp2);
\nit cnt = 0;
\nit sum1, sum2;
\nsum1 = sum2 = 0;
\nrep(l, 1, n + 1)
\n{
\nif (x[l])
\n{
\ntmp1[cnt++] = l;
\nsum1 += l;
\n}
\n}
\ncnt = 0;
\nrep(l, 1, n + 1)
\n{
\nif (bestx[l])
\n{
\ntmp2[cnt++] = l;
\nsum2 += l;
\n}
\n}
\nif (sum1 < sum2)
\n{
\nbestp = cp;
\nbestw = cw;
\nfor (int l = 0; l <= n; l++) bestx[l] = x[l]; return; } if (sum1 > sum2)
\n{
\nreturn;
\n}
\nbool f = false;
\nfor (int l = 0;; ++l)
\n{
\nif (tmp1[l] == 0 && tmp2[l] != 0)
\n{
\nf = true;
\nbreak;
\n}
\nif (tmp1[l] == tmp2[l])continue;
\nif (tmp1[l] != 0 && tmp2[l] == 0)break;
\nif (tmp1[l] < tmp2[l]) { f = true; break; } if (tmp1[l] > tmp2[l])continue;
\n}
\nif (f)
\n{
\nbestp = cp;
\nbestw = cw;
\nfor (int l = 0; l <= n; l++) bestx[l] = x[l];
\n}
\n}
\n}
\nelse
\n{
\nfor (j = 0; j <= 1; j++)
\n{
\nx[i] = j;
\nif (cw + x[i] * w[i] <= c)
\n{
\ncw += w[i] * x[i];
\ncp += p[i] * x[i];
\nBacktrack(i + 1, cp, cw);
\ncw -= w[i] * x[i];
\ncp -= p[i] * x[i];
\n}
\n}
\n}
\n}<\/p>\n

int main()
\n{
\n#ifndef ONLINE_JUDGE
\nfreopen(“1001.in”, “r”, stdin);
\nfreopen(“test.out”, “w”, stdout);
\n#endif
\nit T;
\nin(T);
\nrep(kase, 1, T + 1)
\n{
\nms(p), ms(w), ms(x);
\nms(bestx);
\nbestp = 0;
\nbestw = 0;
\nin(c), in(n);
\nrep(i, 1, n + 1)
\n{
\nin(p[i]);
\nin(w[i]);
\n};
\nBacktrack(1, 0, 0);
\nprintf(“Case #%d:\\n”, kase);
\nprintf(“%d %d\\n”, bestp, bestw);
\nbool f = false;
\nrep(i, 1, n + 1)
\n{
\nif (f)
\n{
\nif (bestx[i])printf(” %d”, i);
\n}
\nel
\n{
\nif (bestx[i])
\n{
\nf = true;
\nprintf(“%d”, i);
\n}
\n}
\nif (i == n && f)puts(“”);
\n}
\n}
\nreturn 0;
\n}
\n[\/cc]<\/p>\n","protected":false},"excerpt":{"rendered":"

\u8fd9\u9053\u9898\u521a\u5f00\u59cb\u6837\u4f8b\u6539\u4e86\u597d\u591a\u6b21\uff0c\u641e\u5f97\u524d\u4e00\u4e2a\u5c0f\u65f6\u65e0\u4ece\u4e0b\u624b\u3002\u6298\u817e\u4e861002\u65e0\u679c\u4ee5\u540e\u8f6c1004\uff0c\u540e\u6765\u53d1\u73b0\u662f\u4e00\u4e2a\u7b80\u5355\u76840- […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[1],"tags":[],"class_list":["post-237","post","type-post","status-publish","format-standard","hentry","category-1"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-3P","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/237","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=237"}],"version-history":[{"count":3,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/237\/revisions"}],"predecessor-version":[{"id":240,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/237\/revisions\/240"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}