2340

AcWing2AK

chaser.
NO.1-Finn

werasdxcv345
Refif
s.y.

2010

Dwjaid

acwing_gza

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

const int N = 50;
typedef long long ll;
ll n;
ll f[N][N],root[N][N];

void print(ll l,ll r){
if(l > r) return;
printf("%lld ", root[l][r]);
if(l == r) return;
print(l, root[l][r] - 1);
print(root[l][r] + 1,r);
}
int main()
{
scanf("%lld",&n);
for(int i = 1;i <= n;i ++){
scanf("%lld",&f[i][i]);
root[i][i]=i;
}
for(int len = 1;len < n;len ++)
for(int l = 1,r;r = len + l, r <= n;l ++)
{
f[l][r]=f[l + 1][r]+f[l][l];
root[l][r] = l;
for(int k = l + 1;k < r;k ++){
if(f[l][r] < f[l][k - 1] * f[k + 1][r] + f[k][k]){
f[l][r]=f[l][k - 1] * f[k + 1][r] + f[k][k];
root[l][r]=k;
}
}
}
cout << f[1][n] <<endl;
print(1,n);
return 0;
}


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;
const int N = 15;
int f[2 * N][N][N];
int n;
int a,b,c;
int w[N][N];
int main()
{
cin >> n;
while(cin >> a >> b >> c,a||b||c)
{
w[a][b] += c;
}
for(int k = 2;k <= 2 * n;k ++)
{
for(int x1 = 1;x1 <= n;x1 ++)
{
for(int x2 = 1;x2 <= n;x2 ++)
{

int &t = f[k][x1][x2];
if(k - x1 <= 0 || k - x1 > n || k - x2 <= 0 || k - x2 > n) continue;
int v = w[x1][k - x1];
if(x1 != x2) v += w[x2][k - x2];
t = max(t,f[k - 1][x1 - 1][x2 - 1]);
t = max(t,f[k - 1][x1 - 1][x2]);
t = max(t,f[k - 1][x1][x2 - 1]);
t = max(t,f[k - 1][x1][x2]);
t += v;

}
}
}
cout << f[2 * n][n][n] << endl;
return 0;
}


#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;
int f[1000010],v[1000010],w[1000010],s[1000010];
struct edge{
int v,w;
};
vector <edge> e[1010];
int main()
{
int n,V;
cin>>n>>V;
for(int i = 1;i <= n;i ++)
{
cin >> v[i] >> w[i] >> s[i];
if(s[i] > 0){
for(int k = 1;k <= s[i];k *= 2)
{
s[i] -= k;
e[i].push_back({v[i]*k,w[i]*k});
}
if(s[i] > 0) e[i].push_back({v[i]*s[i],w[i]*s[i]});
}
}
for(int i=1;i<=n;i++)
{
if(s[i]==-1){
for(int j=V;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
else if(s[i]==0){
for(int j=v[i];j<=V;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
else{
for(edge t : e[i])
for(int j = V;j >= t.v;j --)
f[j] = max(f[j],f[j - t.v] + t.w);
}
}
printf("%d\n",f[V]);
return 0;
}


#include<iostream>
#include<cstdio>
#include<algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include<cstring>

using namespace std;
int a[110][110];
int f[110][110];
int n;
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
cin >> a[i][j];

memset(f,0x3f,sizeof f);
f[1][1] = a[1][1];

for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++){
f[i][j] = min(f[i - 1][j] + a[i][j],f[i][j]);
f[i][j] = min(f[i][j - 1] + a[i][j],f[i][j]);
}
cout << f[n][n] <<endl;
return 0;
}


#include<iostream>
#include<cstring>
#include<algorithm>
#include <queue>
#include<cstdio>
#include<cmath>

using namespace std;
int f[110][110],a[110][110];
int main()
{
int T;
cin >> T;
int n,m;
while(T --)
{
memset(f,0,sizeof f);
memset(a,0,sizeof a);
cin >> n >> m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin >> a[i][j];

for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
f[i][j] = max(f[i - 1][j],f[i][j - 1]) + a[i][j];

cout << f[n][m] <<endl;
}
return 0;
}


#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

const int N = 110;
int f[N][N],w[N],root,n,V,v[N];
int e[N << 1],ne[N << 1],h[N << 1],idx;
{
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u)
{
for(int i = h[u];i != -1;i = ne[i])
{
int son = e[i];
dfs(son);
for(int j = V - v[u];j >= 0;j --)
for(int k = 0;k <= j;k ++)
{
f[u][j] = max(f[u][j],f[u][j - k] + f[son][k]);
}
}
for(int j = V;j >= v[u];j --) f[u][j] = f[u][j-v[u]] + w[u];
for(int j = 1;j < v[u];j ++) f[u][j] = 0;
}
int main()
{
cin >> n >> V;
memset(h,-1,sizeof h);
for(int i = 1;i <= n;i ++)
{
int p;
cin >> v[i] >> w[i] >> p;
if(p == -1) root = i;
}
dfs(root);
cout << f[root][V] << endl;
return 0;
}


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>

using namespace std;
const int N = 1e5 + 10;
int t;
int a[N];
int f[N][2];
int n;
int main()
{
cin >> t;
while(t --)
{
memset(f,0,sizeof f);
memset(a,0,sizeof a);
f[0][0] = 0;
f[0][1] = -0x3f3f3f3f;
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++)
{
f[i][0] = max(f[i - 1][0],f[i - 1][1]);
f[i][1] = f[i - 1][0] + a[i];
}
cout << max(f[n][0], f[n][1]) <<endl;
}
return 0;
}


#include<iostream>
#include<cstdio>
#include <queue>
#include<algorithm>
#include<cstring>
#include <cmath>

using namespace std;
int n,m;
const int N = 1e6 + 10;
int q[N],a[N],sum[N];
int ans=-0x3f3f3f3f;
int hh,tt=-1;
int main()
{
cin>>n>>m;

for(int i = 1;i <= n;i ++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
ans=max(a[i],ans);
}
for(int i = 0;i <= n;i ++)
{
if(hh<=tt&&i-q[hh]>m) hh++;
while(hh<=tt&&sum[q[tt]]>=sum[i]) tt--;
q[++tt]=i;
if(q[hh]!=q[tt])
ans=max(ans,sum[q[tt]]-sum[q[hh]]);
}
cout<<ans<<endl;
return 0;
}


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>

using namespace std;
int v[5] = {0,10,20,50,100};
int f[1000010];
int n;
int main()
{
cin >> n;
f[0] = 1;
for(int i = 1;i <= 4;i ++)
{
for(int j = v[i];j <= n;j ++)
{
f[j] += f[j - v[i]];
}
}
cout << f[n] <<endl;
return 0;
}


#include<iostream>
#include<cstdio>
#include <queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>

using namespace std;
const int N = 12;
const int M = 1 << N,K = 220;
long long f[N][K][M];
vector<int> state;
int n,k;
int cnt[M];
bool check(int state){
for(int i = 0;i < n;i ++)
if((state>>i&1)&&(state>>i+1&1))
return false;

return true;
}
int count(int state){
int res = 0;

for(int i = 0;i < n;i ++) res+=state>>i&1;

return res;
}
int main()
{
cin >> n >> k;
for(int i = 0;i < 1 << n;i ++)
{
if(check(i)){
state.push_back(i);
cnt[i] = count(i);
}
}
for(int a = 0;a < state.size();a ++)
for(int b = 0;b < state.size();b ++)
{
int i = state[a],j = state[b];
if(!(i&j)&&check(i|j))
{
}
}
f[0][0][0] = 1;
for(int i = 1;i <= n + 1;i ++)
for(int j = 0;j <= k;j ++)
for(int a = 0;a < state.size();a ++)