pku 2184 Cow Exhibition-蒲公英云

pku 2184 Cow Exhibition

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

#include 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 #include #include 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 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; } */