1594

insistance

550W
zypnb
ZDC
Acwing_九日
liukebing
Jettblue
GreatestOliveira

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

#include<iostream>
#include<cstring>

using namespace std;

const int N = 305;

int s[N];
int f[N][N];//f[i][j] 合并第i到第j堆所需的最小代价

int main()
{
int n; cin >> n;

for(int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] += s[i - 1];
}

memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; i++)
f[i][i] = 0;

for(int len = 2; len <= n; len++)
for(int i = 1, j = i + len - 1; j <= n; i++, j++)
for(int k = i; k < j; k++)
f[i][j] = min(f[i][j], s[j] - s[i - 1] + f[i][k] + f[k + 1][j]);

cout << f[1][n];

return 0;
}

#include<iostream>

using namespace std;

const int N = 50005;

int a[N];
int f[N], g[N];

int main()
{
int T; scanf("%d", &T);

while(T--)
{
int n; scanf("%d", &n);

for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);

f[0] = -10005;
for(int i = 1, s = 0; i <= n; i++)
{
s = a[i] + max(s, 0);
f[i] = max(f[i - 1], s);
}

g[n + 1] = -10005;
for(int i = n, s = 0; i; i--)
{
s = a[i] + max(s, 0);
g[i] = max(g[i + 1], s);
}

int ans = -20005;
for(int i = 1; i <= n; i++)
ans = max(ans, f[i] + g[i + 1]);
printf("%d\n", ans);
}

return 0;
}

#include<iostream>

using namespace std;

const int N = 3005;

int a[N], b[N];
int f[N][N];

int main()
{
int n; cin >> n;

for(int i = 1; i <= n; i++)
cin >> a[i];

for(int j = 1; j <= n; j++)
cin >> b[j];

for(int i = 1; i <= n; i++)
{
int maxv = 0;
for(int j = 1; j <= n; j++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv + 1);
if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j]);
}
}

int ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, f[n][i]);
cout << ans;

return 0;
}

#include<iostream>

using namespace std;

const int N = 1005;

char A[N], B[N];
int f[N][N];

int main()
{
int n, m;
cin >> n >> m;

cin >> A + 1 >> B + 1;

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]);
if(A[i] == B[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
}
}

cout << f[n][m];

return 0;
}

#### $O(n^2)$

#include<iostream>

using namespace std;

const int N = 1005;

int a[N];
int f[N];

int main()
{
int n; cin >> n;

for(int i = 1; i <= n; i++)
cin >> a[i];

a[0] = -2e9;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < i; j++)
if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}

int ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, f[i]);

cout << ans;

return 0;
}

#### $O(n \log_2 n)$

#include<iostream>

using namespace std;

const int N = 1005;

int a[N];
int f[N], cnt;

int main()
{
int n; cin >> n;

for(int i = 1; i <= n; i++)
cin >> a[i];

a[0] = -2e9, f[0] = a[0];
for(int i = 1; i <= n; i++)
{
if(a[i] > f[cnt]) f[++cnt] = a[i];
else//*lower_bound(f, f + cnt + 1, a[i]) = a[i];
{
int l = 0, r = cnt;
while(l < r)
{
int mid = l + r >> 1;
if(f[mid] >= a[i]) r = mid;
else l = mid + 1;
}
f[l] = a[i];
}
}

cout << cnt;

return 0;
}

#include<iostream>

using namespace std;

const int N = 505;

int f[N];
int a[N][N];

int main()
{
int n; cin >> n;

for(int i = 0; i < n; i++)
for(int j = 0; j <= i; j++)
cin >> a[i][j];

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

cout << f[0];

return 0;
}

#### 贴一个打表代码

#include<iostream>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N = 105;

int s[3] = {1, 2};
int f[N];

int sg(int x)
{
if(f[x] != -1) return f[x];

unordered_set<int> S;
for(int i = 0; i < 3; i++)
{
if(s[i] <= x) S.insert(sg(x - s[i]));
}

for(int i = 0; ; i++)
{
if(!S.count(i)) return f[x] = i;
}
}

int main()
{
for(int k = 3; k <= 35; k++)
{
printf("******k = %d********\n", k);

s[2] = k;
memset(f, -1, sizeof f);

for(int i = 0; i <= 26; i++)
printf("%2d ", i);
puts("");

for(int i = 0; i <= 26; i++)
{
if(sg(i)) printf("Al ");
else printf("Bo ");
}
puts("");
}

return 0;
}

#include<iostream>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N =  105, M = 10005;

int f[M];
int s[N];
int k, n;

int sg(int x)
{
if(f[x] != -1) return f[x];

unordered_set<int> S;
for(int i = 0; i < k; i++)
{
if(s[i] <= x) S.insert(sg(x - s[i]));
}

for(int i = 0; ; i++)
{
if(!S.count(i)) return f[x] = i;
}
}

int main()
{
cin >> k;
for(int i = 0; i < k; i++)
cin >> s[i];

memset(f, -1, sizeof f);

cin >> n;
int ans = 0;
while(n--)
{
int x; cin >> x;
ans ^= sg(x);
}

if(ans) puts("Yes");
else puts("No");

return 0;
}

#include<iostream>

using namespace std;

int main()
{
int n; cin >> n;

int ans = 0;
while(n--)
{
int x; cin >> x;
ans ^= x;
}

if(ans) puts("Yes");
else puts("No");

return 0;
}

### 只做代码分享

#### 组合数

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 2005, mod = 998244353;

int primes[N], cnt;
int index[N];
bool st[N];

void get_primes(int a, int b)
{
for(int i = 2; i <= a; i++)
{
if(!st[i])
{
primes[cnt++] = i;

for(int j = a; j; j /= i) index[cnt - 1] += j/i;

for(int j = b; j; j /= i) index[cnt - 1] -= j/i;

for(int j = a - b; j; j /= i) index[cnt - 1] -= j/i;
}

for(int j = 0; primes[j] <= a/i; j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}

int qmi(LL a, LL b)
{
LL ans = 1;
for(; b; b >>= 1)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}

return ans;
}

int main()
{
int n, m, k;
cin >> n >> m >> k;

//C(n-1, k) * m * (m-1)^k
get_primes(n - 1, k);

LL ans = (LL)m * qmi(m - 1, k) % mod;
for(int i = 0; i < cnt; i++)
ans = ans * qmi(primes[i], index[i]) % mod;
cout << ans;

return 0;
}

#### dp

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 2005, mod = 998244353;

LL f[N][N];//前 i 个小朋友， 恰好有 j 个小朋友与其左边拿的水果不一样

int main()
{
int n, m, k;
cin >> n >> m >> k;

for(int i = 1; i <= n; i++)
f[i][0] = m;

for(int i = 2; i <= n; i++)
for(int j = 1; j <= min(i, k); j++)
f[i][j] = (f[i-1][j] + f[i-1][j-1] * (m - 1) % mod) % mod;

cout << f[n][k];

return 0;
}

#### 一维

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 2005, mod = 998244353;

LL f[N];

int main()
{
int n, m, k;
cin >> n >> m >> k;

f[0] = m;
for(int i = 2; i <= n; i++)
for(int j = min(i, k); j; j--)
f[j] = (f[j] + f[j-1] * (m - 1) % mod) % mod;

cout << f[k];

return 0;
}