重写个左偏树版的。
每次把不合法的删去,留下剩下的,然后合并上去,总复杂度
#includeusing namespace std; const int MAXN = 100005; struct ltheap { struct node { long long dat; int lc, rc, dist; } tree[MAXN*4]; int top; ltheap(){ top = 0; } int new_node(long long dat) { return tree[++top].dat = dat, tree[top].dist = 0, top; } int merge(int &a, int &b) { if (!a && !b) return 0; if (!a) { a = b; return a; } if (tree[a].dat < tree[b].dat) swap(a, b); merge(tree[a].rc, b); if (tree[tree[a].lc].dist < tree[tree[a].rc].dist) swap(tree[a].lc, tree[a].rc); tree[a].dist = tree[tree[a].rc].dist + (tree[a].rc != 0); return a; } long long pop_top(int nd) { long long ret = tree[nd].dat; tree[nd] = tree[merge(tree[nd].lc, tree[nd].rc)]; return ret; } void touring(int nd, int tab) { if (!nd) return; for (int i = 1; i <= tab; i++) putchar(' '); printf("%lld, dist = %d\n", tree[nd].dat, tree[nd].dist); touring(tree[nd].lc, tab+2); touring(tree[nd].rc, tab+2); } } ltheap; long long c[MAXN], l[MAXN], ans = 0; int lab[MAXN], num[MAXN]; long long cnt[MAXN], M; struct node { int to, next; } edge[MAXN]; int head[MAXN], top = 0; void push(int i, int j) { edge[++top] = (node){j, head[i]}, head[i] = top; } int n, rt; void dfs(int nd) { lab[nd] = ltheap.new_node(c[nd]), cnt[nd] += c[nd], num[nd] = 1; for (int i = head[nd]; i; i = edge[i].next) { int to = edge[i].to; // cout << to << endl; dfs(to), lab[nd] = ltheap.merge(lab[nd], lab[to]); cnt[nd] += cnt[to], num[nd] += num[to]; } while (cnt[nd] > M) cnt[nd] -= ltheap.pop_top(lab[nd]), num[nd]--; // cout << nd << " " << num[nd] << " " << cnt[nd] << " " << l[nd] << endl; ans = max(ans, num[nd]*l[nd]); } int main() { scanf("%d%lld", &n, &M); for (int i = 1; i <= n; i++) { int u; scanf("%d%lld%lld", &u, &c[i], &l[i]); if (u == 0) rt = i; else push(u, i); } dfs(rt); cout << ans << endl; return 0; }
sb题啊就是…脑残了半天
#includeusing namespace std; const int MAXN = 55; char str[MAXN]; int dat[MAXN][MAXN], T; int dp[MAXN][MAXN][MAXN]; // 第i个,前j个,k次 int s[MAXN]; int f[MAXN][MAXN*MAXN], n, m; int main() { scanf("%d%d%d", &n, &m, &T); for (int i = 1; i <= n; i++) { scanf("%s", str+1); for (int j = 1; j <= m; j++) dat[i][j] = str[j]-'0'; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) s[j] = s[j-1]+dat[i][j]; for (int j = 1; j <= m; j++) for (int k = 1; k <= m; k++) for (int l = 0; l < j; l++) dp[i][j][k] = max(dp[i][j][k], dp[i][l][k-1]+max(s[j]-s[l], j-l-(s[j]-s[l]))); } for (int i = 1; i <= n; i++) // dp[i][m][Times] for (int j = 0; j <= T; j++) { for (int k = 0; k <= min(j, m); k++) f[i][j] = max(f[i][j], f[i-1][j-k]+dp[i][m][k]); } cout << f[n][T] << endl; return 0; }
状态设计极其诡异的dp…
首先一个性质是:如果能用大额支付一定不会用小额..这很显然,因此如果用大额
张代替小额票票
张。于是就有了方程:
由于
#includeusing namespace std; const int MAXN = 55, MAXA = 100005; int f[MAXA], n; int a[MAXN], ma; int main() { scanf("%d", &n); memset(f, 127, sizeof f); f[1] = ma = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[1] += a[i], ma = max(ma, a[i]); for (int i = 1; i <= ma; i++) for (int j = 2; j*i <= ma; j++) { int ans = f[i]; for (int k = 1; k <= n; k++) { int tms = a[k]/i/j; ans += tms-tms*j; } f[j*i] = min(f[j*i], ans); } int ans = 233333333; for (int i = 1; i <= ma; i++) { ans = min(ans, f[i]); } cout << ans << endl; return 0; }