Atcoder
A - Frog 1
luogu
设
f
(
i
)
:
f(i):
f(i): 青蛙在
i
i
i 石头的最小费用。
只有两种跳法，暴力枚举转移即可，
O
(
n
)
O(n)
O(n)。
f
(
i
+
1
)
←
min
?
f
(
i
)
+
∣
h
i
?
h
i
+
1
∣
f(i+1)\leftarrow^{\min} f(i)+|h_i-h_{i+1}|
f(i+1)←minf(i)+∣hi??hi+1?∣。
f
(
i
+
2
)
←
min
?
f
(
i
)
+
∣
h
i
?
h
i
+
2
∣
f(i+2)\leftarrow^{\min} f(i)+|h_i-h_{i+2}|
f(i+2)←minf(i)+∣hi??hi+2?∣。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n;
int h[maxn], f[maxn];
int Fabs( int x ) { return x < 0 ? -x : x; }
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i ++ ) scanf( "%d", &h[i] );
memset( f, 0x3f, sizeof( f ) );
f[1] = 0;
for( int i = 1;i < n;i ++ ) {
f[i + 1] = min( f[i + 1], f[i] + Fabs( h[i] - h[i + 1] ) );
f[i + 2] = min( f[i + 2], f[i] + Fabs( h[i] - h[i + 2] ) );
}
printf( "%d\n", f[n] );
return 0;
}
B - Frog 2
luogu
青蛙可以跳的步数变大了，但仍可以直接枚举跳的步数
j
j
j。
设
f
(
i
)
:
f(i):
f(i): 青蛙在石头
i
i
i 上的最小花费。
f
(
i
+
j
)
←
min
?
f
(
i
)
+
∣
h
i
?
h
i
+
j
∣
,
1
≤
j
≤
k
f(i+j)\leftarrow^{\min} f(i)+|h_i-h_{i+j}|,1\le j\le k
f(i+j)←minf(i)+∣hi??hi+j?∣,1≤j≤k。
时间复杂度
O
(
n
k
)
O(nk)
O(nk)。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, k;
int h[maxn], f[maxn];
int Fabs( int x ) { return x < 0 ? -x : x; }
int main() {
scanf( "%d %d", &n, &k );
for( int i = 1;i <= n;i ++ ) scanf( "%d", &h[i] );
memset( f, 0x3f, sizeof( f ) );
f[1] = 0;
for( int i = 1;i < n;i ++ )
for( int j = 1;j <= k;j ++ )
if( i + j <= n )
f[i + j] = min( f[i + j], f[i] + Fabs( h[i] - h[i + j] ) );
printf( "%d\n", f[n] );
return 0;
}
C - Vacation
luogu
设
f
(
i
,
0
/
1
/
2
)
:
f(i,0/1/2):
f(i,0/1/2): 第
i
i
i 天，太朗游泳/捉虫/写作业的最大幸福值。
枚举前一天的状态，相邻两天不同即可。
k
≠
j
∧
f
(
i
?
1
,
k
)
→
f
(
i
,
j
)
k\ne j\wedge f(i-1,k)\rightarrow f(i,j)
k?=j∧f(i?1,k)→f(i,j)。
时间复杂度
O
(
9
n
)
O(9n)
O(9n)。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n;
int v[maxn][3], f[maxn][3];
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i ++ )
for( int j = 0;j < 3;j ++ )
scanf( "%d", &v[i][j] );
for( int i = 1;i <= n;i ++ )
for( int j = 0;j < 3;j ++ )
for( int k = 0;k < 3;k ++ )
if( j == k ) continue;
else f[i][j] = max( f[i][j], f[i - 1][k] + v[i][j] );
printf( "%d\n", max( f[n][0], max( f[n][1], f[n][2] ) ) );
return 0;
}
D - Knapsack 1
luogu
01
01
01 背包问题板题。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int w[105], v[105];
int f[100005];
signed main() {
scanf( "%lld %lld", &n, &m );
for( int i = 1;i <= n;i ++ ) scanf( "%ld %lld", &w[i], &v[i] );
for( int i = 1;i <= n;i ++ )
for( int j = m;j >= w[i];j -- )
f[j] = max( f[j], f[j - w[i]] + v[i] );
int ans = 0;
for( int i = m;i;i -- ) ans = max( ans, f[i] );
printf( "%lld\n", ans );
return 0;
}
E - Knapsack 2
01
01
01 背包问题板题。
上一题是总重量可以用数组开下，这一题不行，但我们发现价值总和不超过
1
e
5
1e5
1e5。
所以
f
(
i
,
j
)
:
f(i,j):
f(i,j): 考虑前
i
i
i 个物品，总价值为
j
j
j 的最小重量。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int w[105], v[105];
int f[100005];
signed main() {
scanf( "%lld %lld", &n, &m );
for( int i = 1;i <= n;i ++ ) scanf( "%ld %lld", &w[i], &v[i] );
memset( f, 0x3f, sizeof( f ) );
f[0] = 0;
for( int i = 1;i <= n;i ++ )
for( int j = 1e5;j >= v[i];j -- )
f[j] = min( f[j], f[j - v[i]] + w[i] );
for( int i = 1e5;~ i;i -- )
if( f[i] <= m ) return ! printf( "%lld\n", i );
return 0;
}
F - LCS
luogu
设
f
(
i
,
j
)
:
f(i,j):
f(i,j):
s
s
s 串前
i
i
i 个字母和
t
t
t 串前
j
j
j 个字母的最长公共子序列。
f
(
i
,
j
)
=
max
?
{
f
(
i
?
1
,
j
)
,
f
(
i
,
j
?
1
)
}
f(i,j)=\max\{f(i-1,j),f(i,j-1)\}
f(i,j)=max{f(i?1,j),f(i,j?1)}。
如果
s
i
=
t
j
s_i=t_j
si?=tj? 则还有一种转移：
f
(
i
,
j
)
←
f
(
i
?
1
,
j
?
1
)
+
1
f(i,j)\leftarrow f(i-1,j-1)+1
f(i,j)←f(i?1,j?1)+1。
输出方案就直接从
(
n
,
m
)
(n,m)
(n,m) 开始往前找
f
f
f 相同或者
s
n
=
t
m
s_n=t_m
sn?=tm? 时相差为
1
1
1，递归输出。
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)。
#include <bits/stdc++.h>
using namespace std;
#define maxn 3005
int f[maxn][maxn], g[maxn][maxn];
char s[maxn], t[maxn];
int n, m;
void print( int x, int y ) {
if( ! x or ! y ) return;
if( f[x][y] == f[x - 1][y - 1] + 1 and s[x] == t[y] ) {
print( x - 1, y - 1 );
printf( "%c", s[x] );
}
else if( f[x][y] == f[x - 1][y] ) print( x - 1, y );
else print( x, y - 1 );
}
int main() {
scanf( "%s %s", s + 1, t + 1 );
int n = strlen( s + 1 );
int m = strlen( t + 1 );
for( int i = 1;i <= n;i ++ )
for( int j = 1;j <= m;j ++ ) {
if( s[i] == t[j] ) f[i][j] = max( f[i - 1][j - 1] + 1, f[i][j] );
f[i][j] = max( f[i][j], f[i - 1][j] );
f[i][j] = max( f[i][j], f[i][j - 1] );
}
print( n, m );
return 0;
}
G - Longest Path
luogu
有向无环图。直接拓扑序上
d
p
dp
dp 即可。设
f
(
i
)
:
f(i):
f(i): 到
i
i
i 的最长路径。时间复杂度
O
(
n
)
O(n)
O(n)。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, m;
int d[maxn], f[maxn];
vector < int > G[maxn];
queue < int > q;
int main() {
scanf( "%d %d", &n, &m );
for( int i = 1, x, y;i <= m;i ++ ) {
scanf( "%d %d", &x, &y );
G[x].push_back( y );
d[y] ++;
}
int ans = 0;
for( int i = 1;i <= n;i ++ )
if( ! d[i] ) q.push( i );
while( ! q.empty() ) {
int u = q.front(); q.pop();
ans = max( ans, f[u] );
for( int v : G[u] ) {
f[v] = max( f[v], f[u] + 1 );
if( ! --d[v] ) q.push( v );
}
}
printf( "%d\n", ans );
return 0;
}
H - Grid 1
luogu
设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 到
(
i
,
j
)
(i,j)
(i,j) 位置的方案数。
如果该位置不是障碍，就有转移
f
(
i
,
j
)
=
f
(
i
?
1
,
j
)
+
f
(
i
,
j
?
1
)
f(i,j)=f(i-1,j)+f(i,j-1)
f(i,j)=f(i?1,j)+f(i,j?1)。
时间复杂度
O
(
n
2
)
O(n^2)
O(n2)。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
#define int long long
#define mod 1000000007
char ch[maxn][maxn];
int f[maxn][maxn];
int n, m;
signed main() {
scanf( "%lld %lld", &n, &m );
for( int i = 1;i <= n;i ++ ) scanf( "%s", ch[i] + 1 );
f[1][1] = 1;
for( int i = 1;i <= n;i ++ )
for( int j = 1;j <= m;j ++ )
if( (i ^ 1 or j ^ 1) and ch[i][j] == '.' )
f[i][j] = ( f[i][j - 1] + f[i - 1][j] ) % mod;
printf( "%lld\n", f[n][m] );
return 0;
}
I - Coins
luogu
设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 到第
i
i
i 次翻硬币为止，正面朝上的次数为
j
j
j 的概率。
则
f
(
i
+
1
,
j
+
1
)
←
f
(
i
,
j
)
?
p
i
f(i+1,j+1)\leftarrow f(i,j)*p_i
f(i+1,j+1)←f(i,j)?pi?，
f
(
i
+
1
,
j
)
←
f
(
i
,
j
)
?
(
1
?
p
i
)
f(i+1,j)\leftarrow f(i,j)*(1-p_i)
f(i+1,j)←f(i,j)?(1?pi?)。
还有一种设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 到第
i
i
i 次翻硬币为止，增面朝上的次数比反面朝上的次数多
j
j
j 次的概率。
但
j
j
j 就有可能是负数，就需要整体状态右移为非负数。难写典型的吃力不讨好。
这种把差值当成一维来写，多半是需要优化时空时才考虑的。
#include <bits/stdc++.h>
using namespace std;
#define maxn 6005
int n;
double p[maxn];
double f[maxn][maxn];
int main() {
scanf( "%d", &n );
for( int i = 1;i <= n;i ++ ) scanf( "%lf", &p[i] );
f[0][0] = 1;
for( int i = 1;i <= n;i ++ ) {
f[i][0] = f[i - 1][0] * (1 - p[i]);
for( int j = 1;j <= i;j ++ )
f[i][j] = f[i - 1][j - 1] * p[i] + f[i - 1][j] * (1 - p[i]);
}
double ans = 0;
for( int i = 0;i <= n;i ++ )
if( i > n - i ) ans += f[n][i];
printf( "%.10f\n", ans );
return 0;
}
J - Sushi
题解链接
K - Stones
SG
\text{SG}
SG 函数简单应用。
直接记忆化搜索
f
(
i
)
:
f(i):
f(i): 剩下石子数为
i
i
i 时当前操作的先手必胜
1
1
1 还是必败
0
0
0 。
如果所有后继状态都是必胜态，则该状态必败；否则必胜。
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[105], f[100005];
int dfs( int x ) {
if( x < a[1] ) return f[x] = 0;
if( ~ f[x] ) return f[x];
f[x] = 0;
for( int i = 1;i <= n;i ++ ) {
if( x < a[i] ) continue;
if( ! dfs( x - a[i] ) ) f[x] = 1;
}
return f[x];
}
int main() {
memset( f, -1, sizeof( f ) );
scanf( "%d %d", &n, &k );
for( int i = 1;i <= n;i ++ ) scanf( "%d", &a[i] );
if( dfs( k ) ) puts("First");
else puts("Second");
return 0;
}
L - Deque
luogu
显然区间
d
p
dp
dp。
设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 只剩区间
[
i
,
j
]
[i,j]
[i,j] 中的数，当前先手按最优策略行动的
X
?
Y
X-Y
X?Y。
因为两人都只能从首尾取数，所以剩下来的一定是一段连续区间，就没有枚举
[
i
,
j
]
[i,j]
[i,j] 中的断点
k
k
k 操作。
取了奇数个就是后手操作，减去取
min
?
\min
min；否则是先手操作，加上取
max
?
\max
max。
f
(
i
,
j
)
=
max
?
/
min
?
{
f
(
i
+
1
,
j
)
±
a
i
,
f
(
i
,
j
?
1
)
±
a
i
}
f(i,j)=\max/\min\{f(i+1,j)±a_i,f(i,j-1)±a_i\}
f(i,j)=max/min{f(i+1,j)±ai?,f(i,j?1)±ai?}。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 3005
int n;
int a[maxn];
int f[maxn][maxn];
signed main() {
scanf( "%lld", &n );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
for( int len = 1;len <= n;len ++ )
for( int i = 1;i <= n;i ++ ) {
int j = i + len - 1;
if( j > n ) break;
if( (n - len) & 1 ) f[i][j] = min( f[i + 1][j] - a[i], f[i][j - 1] - a[j] );
else f[i][j] = max( f[i + 1][j] + a[i], f[i][j - 1] + a[j] );
}
printf( "%lld\n", f[1][n] );
return 0;
}
M - Candies
luogu
设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 到第
i
i
i 个小朋友为止，一共分了
j
j
j 颗糖的方案数。
枚举第
i
i
i 个小朋友分的糖数
k
k
k。
f
(
i
,
j
)
=
∑
k
=
0
a
i
f
(
i
?
1
,
j
?
k
)
f(i,j)=\sum_{k=0}^{a_i}f(i-1,j-k)
f(i,j)=∑k=0ai??f(i?1,j?k)。
前缀和优化，
O
(
n
k
)
O(nk)
O(nk)。
g
(
i
,
j
)
=
∑
k
=
0
j
f
(
i
,
j
)
,
f
(
i
,
j
)
=
g
i
?
1
,
j
?
g
i
?
1
,
j
?
a
i
?
1
g(i,j)=\sum_{k=0}^jf(i,j),f(i,j)=g_{i-1,j}-g_{i-1,j-a_i-1}
g(i,j)=∑k=0j?f(i,j),f(i,j)=gi?1,j??gi?1,j?ai??1?。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int f[105][100005];
int n, k;
int a[105];
signed main() {
scanf( "%lld %lld", &n, &k );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
for( int i = 0;i <= k;i ++ ) f[0][i] = 1;
for( int i = 1;i <= n;i ++ ) {
for( int j = 0;j <= k;j ++ )
if( j >= a[i] + 1 ) f[i][j] = ( f[i - 1][j] - f[i - 1][j - a[i] - 1] ) % mod;
else f[i][j] = f[i - 1][j];
if( i ^ n ) for( int j = 1;j <= k;j ++ ) (f[i][j] += f[i][j - 1]) %= mod;
}
printf( "%lld\n", (f[n][k] + mod) % mod );
return 0;
}
N - Slimes
luogu
每次是选相邻两个数合并，显然区间
d
p
dp
dp 枚举断点类型。
设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 合并区间
[
i
,
j
]
[i,j]
[i,j] 的最小代价。
枚举
i
≤
k
<
j
,
f
(
i
,
j
)
←
min
?
f
(
i
,
k
)
+
f
(
k
+
1
,
j
)
+
w
[
i
,
j
]
i\le k<j,f(i,j)\leftarrow\min f(i,k)+f(k+1,j)+w[i,j]
i≤k<j,f(i,j)←minf(i,k)+f(k+1,j)+w[i,j]。
其中
w
[
i
,
j
]
=
∑
k
=
i
j
a
k
w[i,j]=\sum_{k=i}^ja_k
w[i,j]=∑k=ij?ak?，即
a
a
a 的前缀和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 405
int n;
int a[maxn], g[maxn];
int f[maxn][maxn];
signed main() {
scanf( "%lld", &n );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
for( int i = 1;i <= n;i ++ ) g[i] = g[i - 1] + a[i];
memset( f, 0x3f, sizeof( f ) );
for( int i = 1;i <= n;i ++ ) f[i][i] = 0;
for( int len = 1;len <= n;len ++ )
for( int i = 1;i <= n;i ++ ) {
int j = i + len - 1;
if( j > n ) break;
for( int k = i;k < j;k ++ )
f[i][j] = min( f[i][j], f[i][k] + f[k + 1][j] + g[j] - g[i - 1] );
}
printf( "%lld\n", f[1][n] );
return 0;
}
O - Matching
luogu
状压
d
p
dp
dp 即可。
设
f
(
s
,
i
)
:
f(s,i):
f(s,i): 考虑到第一个集合的第
i
i
i 个点的匹配，前面点在第二个集合的匹配点集为
s
s
s 的方案数。
直接枚举不在
s
s
s 中的第二个集合的点
j
j
j，若
i
,
j
i,j
i,j 可以匹配，则转移即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define maxn 21
int f[1 << maxn][maxn];
int g[maxn][maxn];
int n;
signed main() {
scanf( "%lld", &n );
for( int i = 0;i < n;i ++ )
for( int j = 0;j < n;j ++ )
scanf( "%lld", &g[i][j] );
f[0][0] = 1;
for( int i = 0;i < n;i ++ ) {
for( int s = 0;s < (1 << n);s ++ ) {
if( __builtin_popcount( s ) ^ i ) continue;
for( int j = 0;j < n;j ++ )
if( (s >> j & 1) or ! g[i][j] ) continue;
else (f[s | (1 << j)][i + 1] += f[s][i]) %= mod;
}
}
printf( "%lld\n", f[(1 << n) - 1][n] );
return 0;
}
P - Independent Set
luogu
树形
d
p
dp
dp。
设
f
(
u
,
0
/
1
)
:
f(u,0/1):
f(u,0/1): 点
u
u
u 染成白/黑色且子树内染色均合法的方案数。
f
(
u
,
0
)
?
=
(
f
(
v
,
1
)
+
f
(
v
,
0
)
)
;
f
(
u
,
1
)
?
=
f
(
v
,
0
)
f(u,0)*=(f(v,1)+f(v,0));f(u,1)*=f(v,0)
f(u,0)?=(f(v,1)+f(v,0));f(u,1)?=f(v,0)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define maxn 100005
int n;
vector < int > G[maxn];
int f[maxn][2];
void dfs( int u, int fa ) {
f[u][0] = f[u][1] = 1;
for( int v : G[u] ) {
if( v == fa ) continue;
else dfs( v, u );
f[u][0] = f[u][0] * (f[v][1] + f[v][0]) % mod;
f[u][1] = f[u][1] * f[v][0] % mod;
}
}
signed main() {
scanf( "%lld", &n );
for( int i = 1, u, v;i < n;i ++ ) {
scanf( "%lld %lld", &u, &v );
G[u].push_back( v );
G[v].push_back( u );
}
dfs( 1, 0 );
printf( "%lld\n", (f[1][0] + f[1][1]) % mod );
return 0;
}
Q - Flowers
luogu
线段树优化
d
p
dp
dp 转移。
设
f
(
i
)
:
f(i):
f(i): 第
i
i
i 朵花必须留下的最大权值和。
枚举上一朵留下的花
j
j
j ，则
f
(
i
)
=
max
?
j
<
i
∧
h
j
<
h
i
{
f
(
j
)
+
a
i
}
f(i)=\max_{j<i\wedge h_j<h_i}\{f(j)+a_i\}
f(i)=maxj<i∧hj?<hi??{f(j)+ai?}。
将
h
h
h 当作线段树下标建树，
f
f
f 做权值，则合法的
j
j
j 对应树上的一段区间。
只需要维护区间查询最大值以及单点修改即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 200005
int n, ans;
int h[maxn], a[maxn], f[maxn], t[maxn << 2];
#define lson now << 1
#define rson now << 1 | 1
#define mid (l + r >> 1)
void modify( int now, int l, int r, int p, int v ) {
if( l == r ) { t[now] = v; return; }
if( p <= mid ) modify( lson, l, mid, p, v );
else modify( rson, mid + 1, r, p, v );
t[now] = max( t[lson], t[rson] );
}
int query( int now, int l, int r, int L, int R ) {
if( R < l or r < L ) return 0;
if( L <= l and r <= R ) return t[now];
return max(query( lson, l, mid, L, R ), query( rson, mid + 1, r, L, R ));
}
signed main() {
scanf( "%lld", &n );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &h[i] );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
for( int i = 1;i <= n;i ++ ) {
f[i] = query( 1, 1, n, 1, h[i] ) + a[i];
modify( 1, 1, n, h[i], f[i] );
ans = max( ans, f[i] );
}
printf( "%lld\n", ans );
return 0;
}
R - Walk
luogu
设
f
(
i
,
j
)
:
f(i,j):
f(i,j): 第
i
i
i 步后在
j
j
j 点的方案数。
转移则是枚举能到达
j
j
j 点的所有点
k
k
k，
f
(
i
,
j
)
=
∑
g
(
k
,
j
)
=
1
f
(
i
?
1
,
k
)
f(i,j)=\sum_{g(k,j)=1} f(i-1,k)
f(i,j)=∑g(k,j)=1?f(i?1,k)。
转移的
g
g
g 是固定不变的，所以步数可以矩阵加速。
#include <bits/stdc++.h>
using namespace std;
#define maxn 52
#define int long long
#define mod 1000000007
int n, k;
struct matrix {
int c[maxn][maxn];
matrix(){ memset( c, 0, sizeof( c ) ); }
matrix operator * ( matrix &v ) {
matrix ans;
for( int i = 1;i <= n;i ++ )
for( int k = 1;k <= n;k ++ )
for( int j = 1;j <= n;j ++ )
(ans.c[i][j] += c[i][k] * v.c[k][j]) %= mod;
return ans;
}
}f, g;
matrix qkpow( matrix x, int y ) {
matrix ans;
for( int i = 1;i <= n;i ++ ) ans.c[i][i] = 1;
while( y ) {
if( y & 1 ) ans = ans * x;
x = x * x;
y >>= 1;
}
return ans;
}
signed main() {
scanf( "%lld %lld", &n, &k );
for( int i = 1;i <= n;i ++ )
for( int j = 1;j <= n;j ++ )
scanf( "%lld", &g.c[i][j] );
g = qkpow( g, k );
for( int i = 1;i <= n;i ++ ) f.c[1][i] = 1;
f = f * g;
int ans = 0;
for( int i = 1;i <= n;i ++ ) (ans += f.c[1][i]) %= mod;
printf( "%lld\n", ans );
return 0;
}
S - Digit Sum
数位
d
p
dp
dp。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int f[10005][105];
int n, m;
char s[10005];
int num[10005];
int dfs( int x, int sum, bool lim ) {
if( ! lim and ~ f[x][sum] ) return f[x][sum];
if( ! x ) return sum == 0;
int up = lim ? num[x] : 9;
int ans = 0;
for( int i = 0;i <= up;i ++ ) {
ans += dfs( x - 1, (sum + i) % m, lim & (i == up) );
ans %= mod;
}
if( ! lim ) f[x][sum] = ans;
return ans;
}
signed main() {
scanf( "%s %lld", s + 1, &m );
n = strlen( s + 1 );
reverse( s + 1, s + n + 1 );
for( int i = 1;i <= n;i ++ ) num[i] = s[i] ^ 48;
memset( f, -1, sizeof( f ) );
printf( "%lld\n", (mod - 1 + dfs( n, 0, 1 )) % mod );
return 0;
}
T - Permutation
题解链接
U - Grouping
状压
d
p
dp
dp。
预处理
g
(
s
)
:
g(s):
g(s):
s
s
s 集合内的物品分成一个集合的得分之和。
设
f
(
s
)
:
f(s):
f(s): 若干个分组的集合为
s
s
s 的最大得分之和。
枚举最新加入的分组集合
t
t
t 即可，子集枚举
O
(
3
n
)
O(3^n)
O(3n)。
f
(
s
)
=
max
?
t
?
s
{
f
(
s
⊕
t
)
+
g
(
t
)
}
f(s)=\max_{t\subset s}\{f(s\oplus t)+g(t)\}
f(s)=maxt?s?{f(s⊕t)+g(t)}。
#include <bits/stdc++.h>
using namespace std;
#define maxn 17
#define int long long
int g[1 << maxn];
int f[1 << maxn];
int a[maxn][maxn];
int n;
signed main() {
scanf( "%lld", &n );
for( int i = 0;i < n;i ++ )
for( int j = 0;j < n;j ++ )
scanf( "%lld", &a[i][j] );
for( int s = 0;s < (1 << n);s ++ )
for( int i = 0;i < n;i ++ )
for( int j = i + 1;j < n;j ++ )
if( (s >> i & 1) and (s >> j & 1) )
g[s] += a[i][j];
f[0] = 0;
for( int s = 1;s < (1 << n);s ++ ) {
int ans = -1e18;
for( int t = s;t;t = (t - 1) & s )
ans = max( ans, f[s ^ t] + g[t] );
f[s] = ans;
}
printf( "%lld\n", f[(1 << n) - 1] );
return 0;
}
V - Subtree
题解链接
W - Intervals
题解链接
X - Tower
题解链接
Y - Grid 2
题解链接
Z - Frog 3
luogu
设
f
(
i
)
:
f(i):
f(i): 青蛙在
i
i
i 石头上的最小花费。
f
(
i
)
=
min
?
{
f
(
j
)
+
(
h
i
?
h
j
)
2
+
C
}
=
min
?
{
?
2
h
j
?
h
i
+
f
(
j
)
+
C
}
+
h
i
?
h
i
+
C
f(i)=\min\{f(j)+(h_i-h_j)^2+C\}=\min\{-2h_j*h_i+f(j)+C\}+h_i*h_i+C
f(i)=min{f(j)+(hi??hj?)2+C}=min{?2hj??hi?+f(j)+C}+hi??hi?+C。
李超树板题，也可斜率优化。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 1000005
#define V 1000000
#define lson now << 1
#define rson now << 1 | 1
#define mid (l + r >> 1)
struct node { int k, b; }t[maxn << 2];
int n, C;
int h[maxn], f[maxn];
void build( int now, int l, int r ) {
t[now].k = t[now].b = 1e10;
if( l == r ) return;
build( lson, l, mid );
build( rson, mid + 1, r );
}
int calc( node l, int x ) { return l.k * x + l.b; }
bool cover( node Old, node New, int x ) { return calc( New, x ) <= calc( Old, x ); }
void insert( int now, int l, int r, node New ) {
if( cover( t[now], New, l ) and cover( t[now], New, r ) ) { t[now] = New; return; }
if( l == r ) return;
if( cover( t[now], New, mid ) ) swap( t[now], New );
if( cover( t[now], New, l ) ) insert( lson, l, mid, New );
if( cover( t[now], New, r ) ) insert( rson, mid + 1, r, New );
}
int query( int now, int l, int r, int x ) {
if( t[now].k == 1e10 ) return 1e18;
if( l == r ) return calc( t[now], x );
if( x <= mid ) return min( query( lson, l, mid, x ), calc( t[now], x ) );
else return min( query( rson, mid + 1, r, x ), calc( t[now], x ) );
}
signed main() {
scanf( "%lld %lld", &n, &C );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &h[i] );
build( 1, 1, V );
for( int i = 1;i <= n;i ++ ) {
if(i > 1) f[i] = query( 1, 1, V, h[i] ) + h[i] * h[i] + C;
insert( 1, 1, V, (node){ -2 * h[i], f[i] + h[i] * h[i] } );
}
printf( "%lld\n", f[n] );
return 0;
}
|