spfa判负环,差分约束系统
状态图,隐式图等等
图论最短路算法中一些比较精彩的应用

差分约束

algorithm: system of diffrence constraints\textbf{algorithm:}\ \text{system of diffrence constraints}

  • i,j,xjxibk\forall i, j , \quad x_j - x_i \leqslant b_k
    w(i,j)=bk\Longrightarrow w(i, j) = b_k
    let src, uV(G),w(src,u)=0\textbf{let} \ \text{src, } \forall u \in V(G), w(src, u) = 0

  • run spfa()\text{run } \textbf{spfa}()
    if negative cycle exists, solution=\textbf{if} \ \text{negative cycle exists, } \text{solution}=\emptyset
    if no nega-cycle, solution = []\textbf{if} \ \text{no nega-cycle, } \text{solution = } [\cdots]

proof\textbf{proof}
e(u,v),l(v)>l(u)+w(u,v)\forall e(u, v), \quad l(v) > l(u) + w(u, v)
l(v)>l(u)+w(u,v),w(u,v)<0\sum l(v) > \sum l(u) + \sum w(u, v) , \quad \sum w(u, v) < 0
      ~~~~~~l(v)=l(u)\Rightarrow \sum l(v) = \sum l(u)

uV(G),bellman-Ford never stop, no solution\forall u \in V(G), \text{bellman-Ford never stop, no solution}

problem\textbf{problem}
vv 为终点的边权值减小kk, 以vv 为起点的边权值增加kk
变化后所有边的权值非负,并且尽量大

e(a,b),w(a,b)+ka(k)(a)kb(k)(b)x target:=xmax\begin{gathered} \forall e(a, b), \quad w(a, b) + \sum_{k \rightarrow a}(k)(a)- \sum_{k \rightarrow b} (k)(b) \geqslant x \\ \ \\ \text{target:=} x_{\max} \end{gathered}

  • consider x value range, x is non-negative\textbf{consider} \ x \text{ value range, } x \text{ is non-negative}
    x1x \geqslant 1
  • system of difference constraints\text{system of} \ \textbf{difference} \ \textbf{constraints}
    kb(k)(b)ka(k)(a)w(a,b)x\sum_{k\rightarrow b} (k)(b) - \sum_{k \rightarrow a}(k)(a) \leqslant w(a, b) - x
    w(a,b)xmaxw(a,b)xw(a,b)xminw(a, b) - x_{\max} \leqslant w(a, b) - x \leqslant w(a, b) - x_{\min}
    limlhs(not satisfy)limrhs(satisfy)\lim_{lhs} (\textbf{not} \ \textbf{satisfy}) \longleftrightarrow \lim_{rhs} (\textbf{satisfy})
    不等式右边比左边,更趋向于满足差分约束系统
    x[1,max{w(a,b)}]x \in [1, \max\{w(a, b)\}]

algorithm: binary-search\textbf{algorithm:} \ \textbf{binary-search}
satisfy system, spfa() return true\text{satisfy system, spfa() return true}
not satisfy system, spfa() return false\text{not satisfy system, spfa() return false}
if and only if no nega-Cycle, satisfy\textbf{if} \ \textbf{and} \ \textbf{only} \ \textbf{if} \ \text{no} \text{ nega-Cycle, satisfy}

  • if spfa(xmax+1)=true, solution=\text{if} \ \textbf{spfa}(x_{\max} + 1)=\text{true, solution} = \infty
  • if spfa(xmin)=false, solution=\text{if} \ \textbf{spfa}(x_{\min}) = \text{false, solution} = \emptyset
    check mid(xmin,xmax)mid(L,R)\text{check} \ \textbf{mid}(x_{\min}, x_{\max}) \Leftrightarrow \textbf{mid}(L, R)
          ~~~~~~if mid satisfy ,L=mid, mid \text{if} \ \textbf{mid} \ \text{satisfy }, L = \text{mid}, \ \textbf{mid} \ \uparrow
          ~~~~~~else R=mid, mid \text{else } R = \textbf{mid}, \ \textbf{mid} \ \downarrow

思路还是常见的二分,如果中间值满足
就尝试增加中间值,让它尽可能往not satisfy\textbf{not} \ \textbf{satisfy} 方向靠
直到不满足为止

否则,就减小中间值,让它更容易satisfy\textbf{satisfy}

UVA11478

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
const int maxn = 500 + 10;
const int inf = 0x3f3f3f3f;
int n, m;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
int to, weight;
Edge() {}
Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> edges;

void initG() {
edges.clear();
_for(i, 0, maxn) G[i].clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finished ==
int cnt[maxn], inq[maxn];
int D[maxn];

void initSPFA() {
Set(cnt, 0);
Set(inq, 0);
Set(D, inf);
}

// true: nega-cycle
// false: non-negaCycle
int spfa() {
initSPFA();
queue<int> que;
_rep(i, 1, n) {
D[i] = 0;
que.push(i);
inq[i] = true;
}

while (!que.empty()) {
int x = que.front();
que.pop();
inq[x] = 0;

_for(i, 0, G[x].size()) {
const Edge& e = edges[G[x][i]];
int y = e.to;

if(D[y] > D[x] + e.weight) {
D[y] = D[x] + e.weight;
if(!inq[y]) {
que.push(y);
inq[y] = true;

if(++cnt[y] > n) return true;
}
}
}
}
return false;
}

bool check(int x) {
_for(i, 0, edges.size()) {
edges[i].weight -= x;
}
bool ret = spfa();
_for(i, 0, edges.size()) {
edges[i].weight += x;
}

return !ret;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) == 2) {
initG();

// build graph
int ud = 0;
_for(i, 0, m) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
addEdge(u, v, d);
ud = max(ud, d);
}
// build finished
// x in [1, ud]
//debug(ud);

if(check(ud + 1)) printf("Infinite\n");
else if(!check(1)) printf("No Solution\n");
else {
int ans = 1;
int L = 2, R = ud;

while (L <= R) {
int mid = (L + R) >> 1;
//debug(mid);
if(check(mid)) {
ans = mid;
L = mid + 1;
}
else R = mid - 1;
}
printf("%d\n", ans);
}
}
}

状态图编码问题

colored cubes 为例\textbf{colored} \ \textbf{cubes} \ \textbf{为例}
colored-cubes

群运算观点下的图形变换

POJ2741

change posture of cubes\text{change posture of cubes}
改变cubes\text{cubes}posture\textbf{posture}
本质是一个置换(permutation)\textbf{置换(permutation)}

ΩΩ\Omega \rightarrow \Omega 的变换组成的集合称为置换
Sn=S(Ω)S_n = S(\Omega)

  • Sn 的单位元定义: πSn, πe=π=eπS_n \text{ 的单位元定义: } \forall \pi \in S_n, \ \pi e = \pi = e\pi
          ~~~~~~e:=for i[1,n]e:= \textbf{for} \ \forall i \in [1, n]
              ~~~~~~~~~~A(i)=iA(i) = i

  • π:iπ(i),i=1,2,,n\pi: i \mapsto \pi(i), i = 1, 2, \cdots, n

π:(12ni1i2in) ik{1,2,,n}\begin{gathered} \pi:\left(\begin{array}{ccc} 1 & 2 & \ldots & n \\ i_{1} & i_{2} & \ldots & i_{n} \end{array}\right) \\ \ \\ i_k \in \{1, 2, \cdots, n\} \end{gathered}

      ~~~~~~其本质是构成了一个全排列映射

π:(12n i1i2in)\begin{gathered} \pi:\left(\begin{array}{ccc} 1 & 2 & \ldots & n \\ \downarrow & \downarrow & \ & \downarrow \\ i_{1} & i_{2} & \ldots & i_{n} \end{array}\right) \end{gathered}

  • SnS_n 上的乘法运算其实是置换的合成
    构成了nn 元对称群

example\textbf{example}
colored-cubes02

algorithm1\textbf{algorithm1}
permutation groups\textbf{permutation} \ \textbf{groups}

  • for i[1,n],e:A(i)=i\textbf{for} \ \forall i \in [1, n], e:\Rightarrow A(i) = i

πleftA=D trans=πleft,rot(trans, A):\begin{gathered} \pi_{\text{left}} A= D \Rightarrow \\ \ \\ \textbf{trans} = \pi_{\text{left}}, \quad \textbf{rot}\text{(trans, A):} \end{gathered}

      ~~~~~~for i[1,n],let e=[A(i)]\textbf{for} \ \forall i \in [1, n], \textbf{let} \ e = [A(i)]
          ~~~~~~~~~~eg: πleft(i)=p\text{eg: }\quad \pi_{\text{left}}(i) = p
          ~~~~~~~~~~D=πk=(πkπk1π2π1)eD=\pi^{k} = (\pi_k\pi_{k-1}\cdots \pi_2\pi_1) e
          ~~~~~~~~~~D(i)=trans(A(i)), return DD(i) = \textbf{trans(A(i))}, \text{ return } D

algorithm2 逆运算\textbf{algorithm2} \ \textbf{逆运算}

(π1π2πk)A=D A=(πk1)(πk11)(π11)D\begin{gathered} (\pi_1 \pi_2 \cdots \pi_k) A = D \Longrightarrow \\ \ \\ A = (\pi_k^{-1})(\pi_{k-1}^{-1}) \cdots (\pi_1^{-1})D \end{gathered}

permutation inversion\textbf{permutation} \ \textbf{inversion}
      ~~~~~~for x[1,n]\textbf{for} \ \forall x \in [1, n]
          ~~~~~~~~~~π(x)=p\pi(x) = p
          ~~~~~~~~~~do A(p)A(x)\textbf{do} \ A(p) \gets A(x)

main algorithm\textbf{main} \ \textbf{algorithm}

check()\textbf{check()}
get inversion: ori(i)cube(i)\text{get inversion: } ori(i) \gets cube(i)

for kfaces[0,1,,5],tot=0\textbf{for} \ \forall k \in \textbf{faces}[0, 1, \cdots, 5], \textbf{tot} = 0
      ~~~~~~get  Max-color\text{get } \ \textbf{Max-color}
      ~~~~~~for iori[1,,n]\textbf{for} \ \forall i \in \text{ori}[1, \cdots, n]
          ~~~~~~~~~~Max-color=max(Max-color, cnt(ori(i,k)))\textbf{Max-color=} \max(\textbf{Max-color}, \ \textbf{cnt}(ori(i, k)))
      ~~~~~~tot=(ncolored-Max-face)\text{tot} = \sum (n - \textbf{colored-Max-face})
ans = min(ans, tot)\textbf{ans} \ \text{=} \ \min(\textbf{ans,} \ \textbf{tot})

dfs(d)\textbf{dfs}(d)
      ~~~~~~for i[0,23)\textbf{for} \ \forall i \in [0, 23)
          ~~~~~~~~~~cube(d) shapes as posture R(d)=i\text{cube(d) shapes as } \textbf{posture} \ R(d) = i
          ~~~~~~~~~~dfs(d+1)\textbf{dfs}(d + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

// == enumerate permutation ==
/*
int LEFT[] = {4, 0, 2, 3, 5, 1};
int UP[] = {2, 1, 5, 0, 4, 3};

void rot(int *trans, int *A) {
int q[6];
memcpy(q, A, sizeof(q));
_for(i, 0, 6) A[i] = trans[q[i]];
}

void enumerate() {
int E[6] = {0, 1, 2, 3, 4, 5};

_for(i, 0, 6) {
int A[6];
memcpy(A, E, sizeof(E));
if(i == 0) rot(UP, A);
if(i == 1) {
rot(LEFT, A);
rot(UP, A);
}
if(i == 3) {
rot(UP, A);
rot(UP, A);
}
if(i == 4) {
rot(LEFT, A);
rot(LEFT, A);
rot(LEFT, A);
rot(UP, A);
}
if(i == 5) {
rot(LEFT, A);
rot(LEFT, A);
rot(UP, A);
}

_for(k, 0, 4) {
printf("{%d, %d, %d, %d, %d, %d},\n", A[0], A[1], A[2], A[3], A[4], A[5]);
rot(LEFT, A);
}
}
}
// == enumerate finsihed ==

int main() {
freopen("out.txt", "w", stdout);
enumerate();
}
*/

/*
{2, 1, 5, 0, 4, 3},
{2, 0, 1, 4, 5, 3},
{2, 4, 0, 5, 1, 3},
{2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1},
{5, 2, 1, 4, 3, 0},
{1, 2, 0, 5, 3, 4},
{0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5},
{4, 0, 2, 3, 5, 1},
{5, 4, 2, 3, 1, 0},
{1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0},
{1, 0, 3, 2, 5, 4},
{0, 4, 3, 2, 1, 5},
{4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4},
{0, 3, 1, 4, 2, 5},
{4, 3, 0, 5, 2, 1},
{5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2},
{3, 5, 1, 4, 0, 2},
{3, 1, 0, 5, 4, 2},
{3, 0, 4, 1, 5, 2},
*/


const int D[24][6] = {
{2, 1, 5, 0, 4, 3},
{2, 0, 1, 4, 5, 3},
{2, 4, 0, 5, 1, 3},
{2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1},
{5, 2, 1, 4, 3, 0},
{1, 2, 0, 5, 3, 4},
{0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5},
{4, 0, 2, 3, 5, 1},
{5, 4, 2, 3, 1, 0},
{1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0},
{1, 0, 3, 2, 5, 4},
{0, 4, 3, 2, 1, 5},
{4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4},
{0, 3, 1, 4, 2, 5},
{4, 3, 0, 5, 2, 1},
{5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2},
{3, 5, 1, 4, 0, 2},
{3, 1, 0, 5, 4, 2},
{3, 0, 4, 1, 5, 2}
};

// D[r[i]] get posture of ith cube

int n;
const int maxn = 4;
int ori[maxn][6];
int cube[maxn][6];
int r[maxn];
int ans;
vector<string> data;

void init() {
ans = n * 6;
data.clear();
Set(r, 0);
}

inline int getID(const char *name) {
string str(name);
_for(i, 0, data.size()) {
if(data[i] == str) return i;
}
data.push_back(str);
return data.size() - 1;
}

// == check ==
void inv(int ori[][6], const int cube[][6]) {
_for(i, 0, n) _for(j, 0, 6) {
int p = D[r[i]][j];
ori[i][p] = cube[i][j];
}
}

void check() {
inv(ori, cube);

int tot = 0;
_for(k, 0, 6) {
int Max = 0;
int cnt[maxn * 6];
Set(cnt, 0);
_for(i, 0, n) Max = max(Max, ++cnt[ori[i][k]]);
tot += n - Max;
}
ans = min(ans, tot);
}
// == check finished ==

// == dfs ==
void dfs(int d) {
if(d == n) check();
else {
_for(i, 0, 24) {
r[d] = i;
dfs(d + 1);
}
}
}
// == dfs finished ==

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
init();

// get data of cubes
_for(i, 0, n) _for(j, 0, 6) {
char name[30];
scanf("%s", name);
cube[i][j] = getID(name);
}

dfs(1);

printf("%d\n", ans);
}
}

状态空间建图

UVALive4128

  • state transition equation\textbf{state} \ \textbf{transition} \ \textbf{equation}
    LA4128

ii) start and end state\textbf{ii)} \ \textbf{start} \ \textbf{and} \ \textbf{end} \ \textbf{state}
LA4128

algorithm\textbf{algorithm}

  • hash-coding for every state\textbf{hash-coding} \ \textbf{for} \ \textbf{every} \ \textbf{state}
    for dir,add(0, Hash(r1,c1,dir,1),cost)\textbf{for} \ \forall dir, \quad \textbf{add(0,} \ \textbf{Hash}(r_1, c_1, dir, 1), cost)
    for r, c, according to equation\textbf{for} \ \forall \text{r, c}, \text{ according to equation}
          ~~~~~~u(r,c),v(nr,nc)\textbf{u}(r,c), \textbf{v}(nr, nc)
          ~~~~~~add(Hash(u,dir,doubled),Hash(v,nDir,nDoubled),cost)\textbf{add}(\textbf{Hash}(\textbf{u}, dir, doubled), \textbf{Hash}(\textbf{v}, nDir, nDoubled), cost)

  • run Dijkstra()\textbf{run} \ Dijkstra()
          ~~~~~~for dir[0,4),doubled[0,2)\textbf{for} \ \forall dir \in[0, 4), \forall doubled \in [0,2)
              ~~~~~~~~~~get minD(Hash(end,dir,double))\text{get } \min\textbf{D}(\text{Hash}(\text{end},dir, double))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};
const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
const int inv[] = {2, 3, 0, 1};

const int maxn = 100 + 5;
int R, C, r1, c1, r2, c2;
int cost[maxn][maxn][4];
int N;
const int maxN = maxn * maxn * 8 + 5;
const int inf = 0x3f3f3f3f;

inline int read() {
int x;
scanf("%d", &x);
return x;
}

// == Graph defintion ==
vector<int> G[maxN];

class Edge {
public:
int from, to, weight;
Edge() {}
Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

vector<Edge> edges;

class Node {
public:
int u, dist;
bool operator< (const Node& rhs) const {
return dist > rhs.dist;
}

Node() {}
Node(int u, int d) : u(u), dist(d) {}
};

void initG() {
edges.clear();
_for(i, 0, maxN) G[i].clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

// == build data ==
int id[maxn][maxn][4][2];
int tot = 0;

inline int ID(int r, int c, int dir, int doubled) {
int& x = id[r][c][dir][doubled];
if(x != 0) return x;
x = ++tot;
return x;
}

void init() {
tot = 0;
Set(id, 0);
}
// [1, R], [1, C]
inline bool valid(int r, int c, int dir) {
if(r <= 0 || r > R || c <= 0 || c > C) return false;
return cost[r][c][dir] > 0;
}
// == data finished ==

// == build graph ==
void build() {
_for(dir, 0, 4) if(valid(r1, c1, dir)) {
int u = ID(r1+dr[dir], c1+dc[dir], dir, 1);
assert(u >= 1);
int w = cost[r1][c1][dir] * 2;
addEdge(0, u, w);
}

_rep(r, 1, R) _rep(c, 1, C) _for(dir, 0, 4) if(valid(r, c, inv[dir])) {
_for(nDir, 0, 4) if(valid(r, c, nDir)) {
_for(doubled, 0, 2) {
int nr = r + dr[nDir];
int nc = c + dc[nDir];
int w = cost[r][c][nDir];
int nDoubled = 0;

if(nDir != dir) {
nDoubled = 1;
if(!doubled) w += cost[r][c][inv[dir]];
w += cost[r][c][nDir];
}

addEdge(ID(r, c, dir, doubled), ID(nr, nc, nDir, nDoubled), w);
}
}
}
}
// == build finsihed ==

// == dijkstra ==
int D[maxN], vis[maxN];

void initDij(int st) {
Set(D, inf);
D[st] = 0;
Set(vis, 0);
}

void dijkstra(int st) {
initDij(st);
priority_queue<Node> que;
que.push(Node(st, 0));

while (!que.empty()) {
int x = que.top().u;
que.pop();
if(vis[x]) continue;
vis[x] = 1;

_for(i, 0, G[x].size()) {
const Edge& e = edges[G[x][i]];
int y = e.to;

if(D[y] > D[x] + e.weight) {
D[y] = D[x] + e.weight;
que.push(Node(y, D[y]));
}
}
}
}
// == dijkstra finsihed ==

// == solve ==
void solve(int& ans) {
_for(dir, 0, 4) _for(doubled, 0, 2) {
int ed = ID(r2, c2, dir, doubled);
int res = D[ed];
if(!doubled) res += cost[r2][c2][inv[dir]];
ans = min(ans, res);
}
}
// == solve finsihed ==

int main() {
freopen("input.txt", "r", stdin);
int kase = 0;
while (scanf("%d%d%d%d%d%d", &R, &C, &r1, &c1, &r2, &c2) == 6 && R) {
init();
initG();

// input grid data
_rep(r, 1, R) {
_rep(c, 1, C - 1) cost[r][c][RIGHT] = cost[r][c+1][LEFT] = read();
if(r != R) {
_rep(c, 1, C) cost[r][c][DOWN] = cost[r+1][c][UP] = read();
}
}
N = R*C*8 + 1;

// build graph
build();

// run dijkstra
dijkstra(0);

// solve
int ans = inf;
solve(ans);

printf("Case %d: ", ++kase);
if(ans == inf) printf("Impossible\n");
else printf("%d\n", ans);
}
}

差分dp

差分约束可以解决一系列有条件约束的dp问题
0/1 背包,完全背包等等

Problem Scores

比如说从一类物品中,每次选一个物品, 可以重复
问有多少种选择方法
在此基础上,加入约束条件,就是差分约束dp\text{dp}

algorithm1: dp()\textbf{algorithm1:} \ \text{dp()}

  • 0-1 背包\textbf{0-1} \ \text{背包}

    • f(i,j)=max{f(i1,j)do not use ith itemf(i1,jVi)+win>jViuse ith item\begin{gathered} f(i, j)=\max \left\{\begin{array}{l} f(i-1, j) && \text{do not use ith item} \\ f\left(i-1, j-V_{i}\right)+w_{i} \quad n>j \geqslant V_{i} && \text{use ith item} \end{array}\right. \end{gathered}

    • (i1)update()(i)(i-1) \xrightarrow{update()} (i)
    • for j=n downto Vi\textbf{for} \ \forall j = n \ \textbf{downto} \ V_i
  • 完全背包\textbf{完全背包}

    • f(i,j)=max{f(i1,j)do not use ithf(i,jVi)+wiVij<nuse ith\begin{gathered} f(i, j)=\max \left\{\begin{array}{l} f(i-1, j) && \text{do not use ith} \\ f\left(i, j-V_{i}\right)+w_{i} \quad V_i \leqslant j < n && \text{use ith} \end{array}\right. \end{gathered}

    • (i)update()(ith itself)(i) \xrightarrow{update()} (i\textbf{th} \ \textbf{itself})
    • for j=Vi to n\textbf{for} \ \forall j = V_i \ \textbf{to} \ n

dp
一个是用以前的阶段更新现在阶段
一个是用当前阶段更新当前
所以循环的顺序是不一样的

algorithm2\textbf{algorithm2}
1ain,k,1k<n1 \leqslant a_i \leqslant n, \forall k, 1 \leqslant k < n
都有对任意大小为kk 的子集SS 和大小为k+1k+1 的子集TT

xSax<xTax\sum_{x \in S} a_x < \sum_{x \in T} a_x

这样的集合有多少个?

i)\textbf{i)}

ifk=n2 meet the conditions  i=1k+1aii=nk+1nai,(nk+1=k+1k=n2)\begin{gathered} \textbf{if}\quad k = \lfloor \frac{n}{2} \rfloor \text{ meet the conditions } \\ \ \\ \sum_{i = 1}^{k+1}a_i \geqslant \sum_{i = n-k+1}^{n} a_i, \quad (n-k+1= k+1 \Rightarrow k = \lfloor \frac{n}{2}\rfloor) \end{gathered}

根据序列的单调性,k<n2 相当于(i=1k+1ai)ap??(i=nk+1nai)+aq,(ap<aq, p<q), 不等式仍然成立\begin{gathered} \text{根据序列的单调性,} k < \lfloor \frac{n}{2}\rfloor \\ \ \\ \text{相当于} (\sum_{i = 1}^{k+1}a_i)-\sum a_p \geqslant?? ( \sum_{i = n-k+1}^{n} a_i) + \sum a_q, \\ \quad (\sum a_p < \sum a_q, \ p < q), \text{ 不等式仍然成立} \end{gathered}

所以只要有 k=n2 成立,所有情况都成立\text{所以只要有 } k = \lfloor \frac{n}{2} \rfloor \text{ 成立,所有情况都成立}

ii) 差分数组的构造\textbf{ii)} \ \textbf{差分数组的构造}

Δai=aiai1 i=1n2+1j=1iΔaji=nn2+1nj=1iΔaj\begin{gathered} \Delta a_i = a_i - a_{i-1} \\ \ \\ \Rightarrow \sum_{i = 1}^{\lfloor \frac{n}{2} \rfloor + 1} \sum_{j=1}^{i} \Delta a_j \geqslant \sum_{i = n - \lfloor \frac{n}{2} \rfloor +1}^{n} \sum_{j=1}^{i} \Delta a_j \end{gathered}

  • if n=odd number,n2=n12\textbf{if} \ n = \textbf{odd} \ \textbf{number}, \lfloor \frac{n}{2} \rfloor = \frac{n-1}{2}

i=1n+12j=1iΔaji=n+12+1nj=1iΔaj 两边+i=1n+12j=1iΔaj2i=1n+12j=1iΔaji=1nj=1iΔaj 2i=1n+12(n+12i+1)Δaii=1n(ni+1)Δai (i=1n(ni+1)2i=1n+12(n+12i+1))Δai0 i=1nCiΔai0 Ci={ni+1i>n+12(ni+1)2(n+12i+1)=i2in+12\begin{gathered} \sum_{i = 1}^{\frac{n+1}{2}} \sum_{j=1}^{i} \Delta a_j \geqslant \sum_{i = \frac{n+1}{2}+1}^{n} \sum_{j=1}^{i} \Delta a_j \\ \ \\ \xrightarrow{\text{两边+}} \sum_{i = 1}^{\frac{n+1}{2}}\sum_{j = 1}^{i} \Delta a_j \Rightarrow 2\sum_{i = 1}^{\frac{n+1}{2}} \sum_{j=1}^{i} \Delta a_j \geqslant \sum_{i = 1}^{n} \sum_{j=1}^{i} \Delta a_j \\ \ \\ 2\sum_{i=1}^{\frac{n+1}{2}}(\frac{n+1}{2}-i+1)\Delta a_i \geqslant \sum_{i=1}^{n} (n-i+1) \Delta a_i \\ \ \\ (\sum_{i = 1}^{n}(n-i+1) - 2\sum_{i = 1}^{\frac{n+1}{2}}(\frac{n+1}{2}-i+1)) \Delta a_i \leqslant 0 \\ \ \\ \sum_{i = 1}^{n} C_i \Delta a_i \leqslant 0 \\ \ \\ C_{i}=\left\{\begin{gathered} n-i+1 && i>\frac{n+1}{2} \\ (n-i+1)-2\left(\frac{n+1}{2}-i+1\right)= i-2&& i \leqslant \frac{n+1}{2} \end{gathered}\right. \end{gathered}

  • if n=even number,n2=n2\textbf{if} \ n = \textbf{even} \ \textbf{number}, \lfloor \frac{n}{2} \rfloor = \frac{n}{2}

i=1n2+1j=1iΔaji=n2+1nj=1iΔaj减掉i=n/2+1这一项 i=1n2j=1iΔaji=n2+2nj=1iΔaj 2i=1n2j=1iΔaji=1nj=1iΔaji=1n2+1Δai 2i=1n2(n2i+1)Δaii=1n(ni+1)Δaii=1n2+1Δai i=1nCiΔai0 Ci={ni+1i>n2+1i2in2nii=n2+1\begin{gathered} \sum_{i=1}^{\frac{n}{2}+1} \sum_{j=1}^{i} \Delta a_{j} \geqslant \sum_{i=\frac{n}{2}+1}^{n} \sum_{j=1}^{i} \Delta a_{j} \xrightarrow{\text{减掉}i = n/2+1 \text{这一项}} \\ \ \\ \sum_{i=1}^{\frac{n}{2}} \sum_{j=1}^{i} \Delta a_{j} \geqslant \sum_{i=\frac{n}{2}+2}^{n} \sum_{j=1}^{i} \Delta a_{j} \\ \ \\ 2\sum_{i=1}^{\frac{n}{2}} \sum_{j=1}^{i} \Delta a_{j} \geqslant \sum_{i=1}^{n} \sum_{j=1}^{i} \Delta a_{j} - \sum_{i=1}^{\frac{n}{2}+1} \Delta a_{i} \\ \ \\ 2 \sum_{i=1}^{\frac{n}{2}}\left(\frac{n}{2}-i+1\right)\Delta a_{i} \geqslant \sum_{i=1}^{n}(n-i+1) \Delta a_{i}-\sum_{i=1}^{\frac{n}{2}+1} \Delta a_{i} \\ \ \\ \sum_{i = 1}^{n} C_i \Delta a_i \leqslant 0 \\ \ \\ C_{i}=\left\{\begin{gathered} n-i+1 && i>\frac{n}{2} +1\\ i-2&& i \leqslant \frac{n}{2} \\ n-i && i = \frac{n}{2}+1 \end{gathered}\right. \end{gathered}

i=n2+1Ci=n21Ci=i2 Ci={ni+1i>n2+1i2in2+1\begin{gathered} i = \frac{n}{2} + 1 \Rightarrow C_i = \frac{n}{2}-1 \Rightarrow C_i = i - 2 \\ \ \\ C_{i}=\left\{\begin{gathered} n-i+1 && i>\frac{n}{2} +1\\ i-2&& i \leqslant \frac{n}{2}+1 \end{gathered}\right. \end{gathered}

iii)\textbf{iii)}
综上所述

Ci={ni+1i>n2+1i2in2+1 i=1nCiΔai0\begin{gathered} C_{i}=\left\{\begin{gathered} n-i+1 && i>\lfloor \frac{n}{2} \rfloor +1\\ i-2&& i \leqslant \lfloor \frac{n}{2}\rfloor + 1 \end{gathered}\right. \\ \ \\ \sum_{i = 1}^{n} C_i \Delta a_i \leqslant 0 \end{gathered}

i=1,C1=1<0i = 1, C_1 = -1 <0
Δai+1n\sum \Delta a_i + 1 \leqslant n

{a1n1i=2naia1i=2nai\begin{gathered} \left\{\begin{gathered} a_{1} \leqslant n-1-\sum_{i=2}^{n} a_{i} \\ a_{1} \geqslant \sum_{i=2}^{n} a_{i} \end{gathered}\right. \end{gathered}

由此原问题转换为求满足条件a1a_1 的个数

cnt=(n1i=2nai)(i=2nCiai)+1 =ni=2n(Ci+1)ai\begin{gathered} \textbf{cnt} = ( n-1-\sum_{i=2}^{n} a_{i} ) - (\sum_{i = 2}^{n} C_ia_i) +1 \\ \ \\ = n-\sum_{i=2}^{n} (C_i+1)a_{i} \end{gathered}

iv) algorithm\textbf{iv)}\ \textbf{algorithm}

f(i):=i=2n(Ci+1)ai=i 方案数 max{0,ni=2n(Ci+1)ai},i[0,n1] ans = i=0n1(ni)f(i)\begin{gathered} f(i) :=\Rightarrow \sum_{i=2}^{n} (C_i+1)a_{i}=i \\ \ \\ \text{方案数} \\ \ \\ \max\{0, n-\sum_{i=2}^{n} (C_i+1)a_{i}\}, \quad i \in [0, n-1] \\ \ \\ \text{ans = } \sum_{i = 0}^{n-1} (n-i) \cdot f(i) \end{gathered}

  • calculate f(i)\textbf{calculate} \ f(i), 使用完全背包
    此时从i[2,n]\forall i \in[2, n] 的物品中选
    ii 个物品重量为Bi=Ci+1B_i = C_i + 1
    可以重复选, 每种物品可以选aia_i
    其中背包总重量不超过n1n-1, 求方案数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int maxn = 5000 + 10;
int n, m;
int f[maxn], C[maxn];

void initDP() {
Set(f, 0);
f[0] = 1;

int mid = n >> 1;
_rep(i, 2, mid + 1) C[i] = i - 1;
_rep(i, mid + 2, n) C[i] = n - i + 2;
}

int dp() {
initDP();

_rep(i, 2, n) _rep(j, C[i], n - 1) {
f[j] = (f[j] + f[j - C[i]]) % m;
}

ll ans = 0;
_rep(i, 0, n - 1) {
ans = ans + 1ll * (n - i) * f[i] % m;
ans %= m;
}
return ans;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

int res = dp();
cout << res << endl;
}