pku 2184 Cow Exhibition

r囧r小猫 2022-08-13 12:56 14阅读 0赞

\#include <iostream> using namespace std; \#define BASE 100050 int c\[200100\]; bool flag\[200100\]; int main() \{ int N; int i, j; int f, s; scanf("%d", &N); memset(c, 0xbf, sizeof(c)); c\[BASE\] = 0; flag\[BASE\] = true; int max = BASE, min = BASE; for(i = 1; i <= N; ++i) \{ scanf("%d%d", &s, &f); if(s < 0) \{ for(j = min; j <= max; ++j) if(flag\[j\] && c\[j\] + f > c\[j+s\]) \{ c\[j+s\] = c\[j\] + f; flag\[j+s\] = true; \} min += s; \} else \{ for(j = max; j >= min; --j) if(flag\[j\] && c\[j\] + f > c\[j+s\]) \{ c\[j+s\] = c\[j\] + f; flag\[j+s\] = true; \} max += s; \} \} int Max = BASE; for(i = BASE; i <= max; ++i) if(c\[i\] >= 0 && c\[i\]+i > Max) Max = c\[i\]+i; printf("%d/n", Max-BASE); return 0; \} /\* \#include <iostream> \#include <climits> \#include <exception> using namespace std; \#define BASE 100000 int c\[BASE\*2\]; int s\[101\]; int f\[101\]; int main() \{ int N; int i, j; scanf("%d", &N); for(i = 1; i <= N; ++i) scanf("%d%d", &s\[i\], &f\[i\]); memset(c, 0xbf, sizeof(c)); c\[BASE\] = 0; for(i = 1; i <= N; ++i) for(j = BASE; j >= -BASE; --j) if(BASE+j-s\[i\] >= 0) \{ if(c\[BASE+j-s\[i\]\] + f\[i\] > c\[BASE+j\]) c\[BASE+j\] = c\[BASE+j-s\[i\]\]+f\[i\]; \} int max = INT\_MIN; for(i = -BASE; i <= BASE; ++i) if(c\[BASE+i\]+i>=0 && c\[BASE+i\]+i > max) max = c\[BASE+i\]+i; if(max >= 0) printf("%d/n", max-BASE); else printf("0/n"); return 0; \}\*/ /\* \#include <iostream> using namespace std; int s\[101\]; int f\[101\]; \#define BASE 100000 int c\[BASE + 100001\]; int ff\[BASE + 100001\]; int ss\[BASE + 100001\]; int main() \{ int N; int i , j; scanf("%d", &N); for(i = 1; i <= N; ++i) scanf("%d%d", &s\[i\], &f\[i\]); for(i = 1; i <= N; ++i) for(j = BASE; j >= -BASE; --j) if(BASE+j-(s\[i\]+f\[i\]) >= 0 && c\[BASE+j-(s\[i\]+f\[i\])\] + s\[i\]+f\[i\] > c\[BASE+j\]) \{ c\[BASE+j\] = c\[BASE+j-(s\[i\]+f\[i\])\] + s\[i\]+f\[i\]; ss\[BASE+j\] = ss\[BASE+j-(s\[i\]+f\[i\])\] + s\[i\]; ff\[BASE+j\] = ff\[BASE+j-(s\[i\]+f\[i\])\] + f\[i\]; \} for(i = BASE; i >= -BASE; --i) if(ss\[BASE+i\] >= 0 && ff\[BASE+i\] >= 0) \{ printf("%d/n", c\[BASE+i\]); break; \} if(i == -1-BASE) printf("%d/n", 0); return 0; \} \*/