3944

linzy_3

North_Pole

._6372
AIC

novice_7

slight

wdyf
mei_24
PekingOpera
K777

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 105, M = 100005;
int n, m;
int a[N], c[N];
int f[M], used[M]; //j是否能被拼成，used表示拼到j用了多少个第i个物品，只枚举倍数

void init()
{
rep(i, 0, m + 1)
f[i] = 0;
}

int main()
{
while(scanf("%d%d", &n, &m))
{
if(!n && !m)    break;
init();

rep(i, 1, n + 1)
scanf("%d", &a[i]);
rep(i, 1, n + 1)
scanf("%d", &c[i]);

f[0] = 1;
rep(i, 1, n + 1)
{
rep(j, 0, m + 1)
used[j] = 0;
rep(j, a[i], m + 1)
if(!f[j] && f[j - a[i]] && used[j - a[i]] < c[i]) //类单调队列优化
f[j] = 1, used[j] = used[j - a[i]] + 1;
}
int res = 0;
rep(i, 1, m + 1)
if(f[i])
res ++;
cout << res << '\n';
}
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 200005;
int n;
int flow[N]; //以i为根节点的整个子树的流量
int f[N]; //以i为根节点的整个子树的最大流量
vector<PII> g[N];
int deg[N]; //每个点的度数

void dp1(int u, int fa)
{
flow[u] = 0;
for(PII x : g[u])
{
int v = x.first, w = x.second;
if(v == fa)  continue;
dp1(v, u);
if(deg[v] == 1) flow[u] += w;
else flow[u] += min(w, flow[v]);
}
}

void dp2(int u, int fa)
{
for(PII x : g[u])
{
int v = x.first, w = x.second;
if(v == fa) continue;
if(deg[u] == 1)
f[v] = flow[v] + w; //如果父亲是汇点，那么制约的就只有w了
else if(deg[v] == 1)
f[v] = min(w, flow[u] - w); //如果当前点为汇点，他以自身为子树为0，另一部分是父亲总流量-边和边的最小值
else
f[v] = flow[v] + min(f[u] - min(w, flow[v]), w); //如果都不是，那么他首先拥有自己的子树，还要加上来自父亲那边的总流量-父亲分过来的流量
dp2(v, u);
}
}

void init()
{
rep(i, 1, n + 1)
g[i].clear(), deg[i] = 0;
}

void solve()
{
cin >> n;
init();

for(int i = 1; i < n; i ++)
{
int u, v, c;
cin >> u >> v >> c;
g[u].pb({v, c}); g[v].pb({u, c});
deg[v] ++; deg[u] ++; //统计度数
}

dp1(1, -1);
f[1] = flow[1];
dp2(1, -1);
int res = 0;
rep(i, 1, n + 1)
res = max(res, f[i]);
cout << res << '\n';
}

signed main()
{
int _ = 1;
cin >> _;
while(_--)
solve();
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 305;
int n, m;
int f[N][N]; //以i为根的子树下，选择了j门课的方案的最大值
int a[N];
vector<int> g[N];
int rt = 0;

void dp(int u)
{
f[u][0] = 0;
for(int v : g[u])
{
dp(v);
//for(int v : g[u])
for(int j = m; j >= 0; j --) //当前以i为根的子树能选的数量
for(int k = 0; k <= j; k ++) //组内的物品
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
//分组背包
}
if(u != 0) //如果u不为0，那么我们最多选j-1节课，为了避免分类讨论所以写在外卖
for(int j = m; j > 0; j --)
f[u][j] = f[u][j - 1] + a[u];
}

signed main()
{
cin >> n >> m;
rep(i, 1, n + 1)
{
int fa;
cin >> fa >> a[i];
g[fa].pb(i);
}

dp(0);
cout << f[0][m] << '\n';
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 305;
const int mod = 1e9;
char s[N];
int f[N][N];
int n;

signed main()
{
scanf("%s", s + 1);
n = strlen(s + 1);

rep(len, 1, n + 1)
rep(l, 1, n - len + 2)
{
int r = l + len - 1;
if(len == 1)    f[l][r] = 1;
else
{
if(s[l] == s[r])
{
for(int k = l + 2; k <= r; k ++)
if(s[l] == s[k]) //[l + 1, k - 1]是s[l]和s[k]夹着的子树
f[l][r] = (f[l][r] + 1ll * f[l + 1][k - 1] * f[k][r]) % mod;
}
}
}
cout << f[1][n] << '\n';
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 105;
int n;
vector<int> g[N];
int dfn[N], low[N];
int block[N];
int scc, timer;
int instk[N];
vector<int> stk;

vector<int> dag[N];
int in[N], out[N];
bool flag[N][N];

void tarjan(int u)
{
dfn[u] = low[u] = ++ timer;
stk.pb(u);
instk[u] = 1;
for(int v : g[u])
{
if(!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else if(instk[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
scc ++;
int top = -1;
do
{
top = stk.back();
stk.pop_back();
block[top] = scc;
instk[top] = 0;
} while(top != u);
}
}

signed main()
{
cin >> n;
rep(i, 1, n + 1)
{
int v;
while(cin >> v)
{
if(!v)  break;
g[i].pb(v);
}
}

rep(i, 1, n + 1)
if(!dfn[i])
tarjan(i);

rep(i, 1, n + 1)
for(int j : g[i])
{
int u = block[i], v = block[j];
if(u == v)  continue;
dag[u].pb(v), out[u] ++, in[v] ++;
}
int tot_in0 = 0, tot_out0 = 0;
rep(i, 1, scc + 1)
{
tot_in0 += (in[i] == 0 ? 1 : 0);
tot_out0 += (out[i] == 0 ? 1 : 0);
}
cout << tot_in0 << '\n';
if(scc == 1) //特判一下
cout << "0\n";
else
cout << max(tot_in0, tot_out0) << '\n';
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 6005;
int n;
int a[N];
int father[N];
vector<int> g[N];
int f[N][2]; //以i为根的子树,i是去还是不去的最大价值

void dfs(int u, int fa)
{
f[u][1] = a[u];
for(auto v : g[u])
{
if(v == fa) continue;
dfs(v, u);
f[u][1] += f[v][0];
f[u][0] += max(f[v][1], f[v][0]);
}
}

signed main()
{
cin >> n;
rep(i, 1, n + 1)
cin >> a[i];
rep(i, 2, n + 1)
{
int u, v;
cin >> v >> u;
g[u].pb(v); g[v].pb(u);
father[v] = 1;
}
int rt = -1;
rep(i, 1, n + 1)
if(!father[i])
{rt = i; break;}

dfs(rt, - 1);
cout << max(f[rt][0], f[rt][1]) << '\n';
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

int n, m;
int f[205][25][805]; //从前i个人里选j个人，且差值为k的方案集合,属性：和的最大值
int p[205], d[205];
int base = 400;
int ans[205];

signed main()
{
int no = 1;
while(scanf("%d%d", &n, &m))
{
if(!n && !m)    break;
rep(i, 1, n + 1)
scanf("%d%d", &p[i], &d[i]);
memset(f, -0x3f, sizeof f);
f[0][0][base] = 0;

for(int i = 1; i <= n; i ++)
for(int j = 0; j <= m; j ++)
for(int k = 0; k <= 800; k ++)
{
f[i][j][k] = f[i - 1][j][k];
int dis = k - (d[i] - p[i]);
if(dis < 0 || dis > 805)   continue;
if(j == 0)   continue;
f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][dis] + (d[i] + p[i]));
}

int v = 0;
while(f[n][m][base - v] < 0 && f[n][m][base + v] < 0)   v ++;

if(f[n][m][base - v] > f[n][m][base + v])   v = base - v;
else v = base + v;

vector<int> res;
int i = n, j = m, k = v;
while(j)
{
if(f[i][j][k] == f[i - 1][j][k])    i --;
else
{
res.pb(i);
k -= (d[i] - p[i]), i --, j --;
}
}

int totp = 0, totd = 0;
for(auto x : res)
totp += p[x], totd += d[x];
printf("Jury #%d\n", no ++);
printf("Best jury has value %d for prosecution and value %d for defence:\n", totp, totd);
sort(res.begin(), res.end());
for(auto x : res)
printf(" %d", x);
puts("\n");
}
return 0;
}


1.如果一条边仅在第二个环出现过，只用走一次。
2.如果一条边在两个环都出现过，要走两次。
3.如果一条边在两个环都没出现过，要走两次。

#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 100005, M = 2 * N;
int h[N], e[M], w[M], nex[M], idx;
{
e[idx] = b;
w[idx] = 1;
nex[idx] = h[a];
h[a] = idx ++;
}

int n, k, d2; //次直径
int dis[N], path[N];

int bfs(int u)
{
memset(dis, -1, sizeof dis);
queue<int> q;
q.push(u);
dis[u] = 0;

while(q.size())
{
int t = q.front();
q.pop();

for(int i = h[t]; i != -1; i = nex[i])
{
int v = e[i];

if(dis[v] != -1)    continue;
dis[v] = dis[t] + 1;
path[v] = i;// 记录路径
q.push(v);
}
}

int p = u;
for(int i = 1; i <= n; i ++)
if(dis[i] > dis[p])
p = i;
return p;
}

void update(int ed, int st)
{
while(ed != st)
{
w[path[ed]] = -1; //正边
w[path[ed] ^ 1] = -1; //神来之笔，因为存入的时候是连续的 所以idx和idx^1一奇一偶正好一起改变了
ed = e[path[ed] ^ 1]; //反边
}
}

int dp(int u, int fa)
{
int dis1 = 0, dis2 = 0;
for(int i = h[u]; i != -1; i = nex[i])
{
int v = e[i], val = w[i];
if(v == fa) continue;
int t = dp(v, u) + val;
if(t >= dis1)
dis2 = dis1, dis1 = t;
else if(t > dis2)
dis2 = t;
}
d2 = max(d2, dis1 + dis2);
return dis1;
}

int main()
{
memset(h, -1, sizeof h);
cin >> n >> k;
for(int i = 2; i <= n; i ++)
{
int u, v;
cin >> u >> v;
}

int st = bfs(1);
int ed = bfs(st);

//若K = 1的时候，连接直径的两端点为最佳方案。K = 2的时候，应该找到最大直径和次大直径
int res = 2 * (n - 1) - dis[ed] + 1;

if(k == 2)
{
update(ed, st);
memset(dis, 0, sizeof dis);
dp(1, -1);
res = res - d2 + 1;
}

cout << res << '\n';
}


#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define per(i, n, a) for(int i = n; i >= a; i--)
#define fi first
#define se second
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
#define ms(x, y)    memset(x, y, sizeof x)
#define debug(x)    cout << x << endl;
typedef double db;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;

#define int long long
const int N = 35;
int n, m;
PII g[N];
int f[N][5005]; //表示将j块饼干分配给前i个人，且分配的饼干数单调不升 属性:Min
int s[N]; //前缀和
int res[N];

int cmp(PII a, PII b)   {return a.first > b.first;}

void solve()
{
cin >> n >> m;
rep(i, 1, n + 1)
cin >> g[i].first, g[i].second = i;
sort(g + 1, g + n + 1, cmp); //贪心 a[i]越大，分的饼干应该越多 通过交换邻项法证明

rep(i, 1, n + 1)    s[i] = s[i - 1] + g[i].first;

ms(f, 0x3f);
f[0][0] = 0;
for(int i = 1; i <= n; i ++)
for(int j = i; j <= m; j ++) //满足j - i >= 0 --> j >= i
{
f[i][j] = f[i][j - i];
for(int k = 1; k <= i; k ++) // i - k >= 0
f[i][j] = min(f[i][j], f[i - k][j - k] + (s[i] - s[i - k]) * (i - k)); //结尾k个人都分到饼干1
}

cout << f[n][m] << '\n';

//倒推DP的过程
int i = n, j = m, h = 0;
while(i) //DP转移过程中已保证i <= j
{
if(f[i][j] == f[i][j - i])  j -= i, h ++; //整体下降的高度是多少
else
{
for(int k = 1; k <= i; k ++)
{
if(f[i][j] == f[i - k][j - k] + (s[i] - s[i - k]) * (i - k)) //找到连续的一段的1
{
for(int l = i - k + 1; l <= i; l ++)
res[g[l].second] = h + 1;
i -= k, j -= k;
break;
}
}
}
}

for(int i = 1; i <= n; i ++)
cout << res[i] << ' ';
cout << '\n';
}

signed main()
{
solve();
}


#include <bits/stdc++.h>

using namespace std;
int n, m;
int g[55][55];
int f[55 << 1][55][55]; //两人一起走的第n + m步, 当前分别位于(i, k - i), (j, k - j)

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> g[i][j];

for(int k = 2; k <= n + m; k ++)
for(int i = 1; i < k; i ++)
for(int j = 1; j < k; j ++)
{
int t = g[i][k - i];
if(i != j)  t += g[j][k - j];
for(int a = 0; a <= 1; a ++)
for(int b = 0; b <= 1; b ++)
f[k][i][j] = max(f[k - 1][i - a][j - b], f[k][i][j]);
f[k][i][j] += t;
}
cout << f[n + m][n][n];
}