2016 UESTC Training for Dynamic Programming
A - 柱爷与咸鱼神功
题意：
柱爷有n(<=5000)点心情去学m(<=5000)个招式,每个招式会得到一定的修炼值,但要消耗一定的心情,求最多的修炼值。
题解：
0.这是一个裸的背包问题，用每一个物品去更新每一种背包的状态.
1.状态定义:dp[i]表示用i点心情得到的最多修炼值。
2.状态转移:dp[i] = max{dp[i-v[j]]+w[j]}
代码：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n,m,v[N],w[N],dp[N];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;++i){
scanf("%d%d",&v[i],&w[i]);
}
for(int i = 1;i <= m;++i){
for(int j = n;j >= v[i];--j)
dp[j] = max(dp[j-v[i]]+w[i],dp[j]);
}
cout<<dp[n]<<endl;
return 0;
}//- xgtao -
B - 柱爷与最大区间和
题意：
给出一个长度为n(<=500000)的序列,输出两个不相邻区间的和。
题解：
0.因为要严格控制不相邻的区间,定义状态f[i][0/1]表示在1~i之前的最大区间和(并且不选或选第i点),g[i][0/1]表示在i~n之前的最大区间和(并且不选或选i点)。
1.f[i][0] = max{f[i-1][0],f[i-1][1]} f[i][1] = max{f[i-1][1]+w[i],w[i]} g[i][0] = max{g[i+1][0],g[i+1][1]} g[i][1] = max{g[i+1][1]+w[i],w[i]}
2.最后的答案即为max{f[i][0]+g[i][0],f[i][0]+g[i][1],f[i][1]+g[i][0]}
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 1<<30;
const int N = 500010;
int f[N][2],g[N][2],a[N],n,ans = -inf;
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%d",&a[i]);
f[0][0] = f[0][1] = -inf,g[n+1][0] = g[n+1][1] = -inf;
for(int i = 1;i <= n;++i){
f[i][1] = max(f[i-1][1]+a[i],a[i]);
f[i][0] = max(f[i-1][1],f[i-1][0]);
}
for(int i = n;i >= 1;--i){
g[i][1] = max(g[i+1][1]+a[i],a[i]);
g[i][0] = max(g[i+1][1],g[i+1][0]);
}
for(int i = 1;i <= n;++i){
int ret = max(max(f[i][0]+g[i+1][1],f[i][0]+g[i][0]),f[i][1]+g[i+1][0]);
ans = max(ans,ret);
}
cout<<ans<<endl;
return 0;
}//- xgtao -
C - 柱爷的下凡
题意：
用三种硬币表示1~n(<=200)的数,并且总共用的硬币数最少,多组数据(<=200)！！！！！
题解：
0.三种硬币中必定包含一枚1元。
1.那么另外两种硬币b,c就可以枚举,定义状态dp[i]表示表示出i元花费最少的硬币数。
2.状态转移即为:dp[i] = max{dp[i-b]+1,dp[i-c]+1,dp[i-1]+1},只需要计算Σdp[1~n]即可。
3.这是O(n^3)的算法,但是有多组数据就是O(n^4)。
4.我们可以通过打表解决,枚举n,预处理出所有n的情况,再用O(1)查询。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500;
int T,n,dp[N],a = 1,ans2[N],ans3[N],ans = 1e9,ret;
int main(){
freopen("C_list.cpp","w",stdout);
ans2[1] = 2,ans3[1] = 3;
ans2[2] = 2,ans3[2] = 3;
ans2[3] = 2,ans3[3] = 3;
for(int i = 4;i <= 200;++i){
ans = 1e9;
for(int j = 2;j < i;++j){
for(int k = j+1;k <= i;++k){
ret = 0;
dp[0] = 0;
for(int c = 1;c <= i;++c){
if(c >= k)dp[c] = min(dp[c-k],min(dp[c-j],dp[c-1]))+1;
else if(c >= j)dp[c] = min(dp[c-j],dp[c-1])+1;
else if(c >= 1)dp[c] = dp[c-1]+1;
}
for(int c = 1;c <= i;++c)ret += dp[c];
if(ret < ans)ans = ret,ans2[i] = j,ans3[i] = k;
}
}
}
for(int i = 1;i <= 200;++i){
printf(" if(n == %d)printf",i);
printf("("1 %d %d\n");
",ans2[i],ans3[i]);
}
return 0;
}
#include <cstdio>
int T,n;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
if(n == 1)printf("1 2 3
");
if(n == 2)printf("1 2 3
");
if(n == 3)printf("1 2 3
");
if(n == 4)printf("1 2 3
");
if(n == 5)printf("1 2 3
");
if(n == 6)printf("1 2 3
");
if(n == 7)printf("1 2 5
");
if(n == 8)printf("1 3 4
");
if(n == 9)printf("1 3 4
");
if(n == 10)printf("1 2 5
");
if(n == 11)printf("1 2 5
");
if(n == 12)printf("1 4 6
");
if(n == 13)printf("1 4 6
");
if(n == 14)printf("1 4 6
");
if(n == 15)printf("1 3 7
");
if(n == 16)printf("1 4 6
");
if(n == 17)printf("1 3 7
");
if(n == 18)printf("1 4 6
");
if(n == 19)printf("1 3 8
");
if(n == 20)printf("1 3 8
");
if(n == 21)printf("1 5 7
");
if(n == 22)printf("1 4 9
");
if(n == 23)printf("1 4 9
");
if(n == 24)printf("1 5 8
");
if(n == 25)printf("1 5 8
");
if(n == 26)printf("1 5 8
");
if(n == 27)printf("1 5 8
");
if(n == 28)printf("1 4 9
");
if(n == 29)printf("1 5 8
");
if(n == 30)printf("1 5 8
");
if(n == 31)printf("1 4 9
");
if(n == 32)printf("1 5 8
");
if(n == 33)printf("1 5 8
");
if(n == 34)printf("1 7 11
");
if(n == 35)printf("1 7 11
");
if(n == 36)printf("1 7 11
");
if(n == 37)printf("1 5 12
");
if(n == 38)printf("1 5 12
");
if(n == 39)printf("1 5 12
");
if(n == 40)printf("1 7 11
");
if(n == 41)printf("1 5 12
");
if(n == 42)printf("1 5 12
");
if(n == 43)printf("1 5 12
");
if(n == 44)printf("1 7 11
");
if(n == 45)printf("1 7 11
");
if(n == 46)printf("1 7 11
");
if(n == 47)printf("1 7 11
");
if(n == 48)printf("1 6 14
");
if(n == 49)printf("1 6 14
");
if(n == 50)printf("1 6 14
");
if(n == 51)printf("1 6 14
");
if(n == 52)printf("1 8 13
");
if(n == 53)printf("1 8 13
");
if(n == 54)printf("1 8 13
");
if(n == 55)printf("1 8 13
");
if(n == 56)printf("1 8 13
");
if(n == 57)printf("1 6 14
");
if(n == 58)printf("1 6 14
");
if(n == 59)printf("1 6 14
");
if(n == 60)printf("1 8 13
");
if(n == 61)printf("1 8 13
");
if(n == 62)printf("1 6 14
");
if(n == 63)printf("1 6 14
");
if(n == 64)printf("1 6 14
");
if(n == 65)printf("1 8 13
");
if(n == 66)printf("1 8 13
");
if(n == 67)printf("1 8 13
");
if(n == 68)printf("1 8 13
");
if(n == 69)printf("1 7 17
");
if(n == 70)printf("1 7 17
");
if(n == 71)printf("1 7 17
");
if(n == 72)printf("1 7 17
");
if(n == 73)printf("1 7 17
");
if(n == 74)printf("1 9 14
");
if(n == 75)printf("1 7 17
");
if(n == 76)printf("1 7 17
");
if(n == 77)printf("1 7 17
");
if(n == 78)printf("1 7 17
");
if(n == 79)printf("1 7 17
");
if(n == 80)printf("1 10 16
");
if(n == 81)printf("1 10 16
");
if(n == 82)printf("1 10 16
");
if(n == 83)printf("1 10 16
");
if(n == 84)printf("1 8 19
");
if(n == 85)printf("1 8 19
");
if(n == 86)printf("1 8 19
");
if(n == 87)printf("1 8 19
");
if(n == 88)printf("1 6 20
");
if(n == 89)printf("1 10 17
");
if(n == 90)printf("1 11 15
");
if(n == 91)printf("1 11 15
");
if(n == 92)printf("1 11 15
");
if(n == 93)printf("1 11 15
");
if(n == 94)printf("1 11 18
");
if(n == 95)printf("1 11 18
");
if(n == 96)printf("1 12 19
");
if(n == 97)printf("1 12 19
");
if(n == 98)printf("1 12 19
");
if(n == 99)printf("1 12 19
");
if(n == 100)printf("1 12 19
");
if(n == 101)printf("1 12 19
");
if(n == 102)printf("1 12 19
");
if(n == 103)printf("1 12 19
");
if(n == 104)printf("1 12 19
");
if(n == 105)printf("1 12 19
");
if(n == 106)printf("1 12 19
");
if(n == 107)printf("1 12 19
");
if(n == 108)printf("1 12 19
");
if(n == 109)printf("1 12 19
");
if(n == 110)printf("1 12 19
");
if(n == 111)printf("1 13 18
");
if(n == 112)printf("1 12 19
");
if(n == 113)printf("1 12 19
");
if(n == 114)printf("1 12 19
");
if(n == 115)printf("1 12 19
");
if(n == 116)printf("1 12 19
");
if(n == 117)printf("1 12 19
");
if(n == 118)printf("1 12 19
");
if(n == 119)printf("1 12 19
");
if(n == 120)printf("1 12 19
");
if(n == 121)printf("1 12 19
");
if(n == 122)printf("1 12 19
");
if(n == 123)printf("1 7 23
");
if(n == 124)printf("1 7 23
");
if(n == 125)printf("1 8 27
");
if(n == 126)printf("1 8 27
");
if(n == 127)printf("1 8 27
");
if(n == 128)printf("1 9 23
");
if(n == 129)printf("1 9 23
");
if(n == 130)printf("1 9 23
");
if(n == 131)printf("1 9 30
");
if(n == 132)printf("1 9 30
");
if(n == 133)printf("1 14 22
");
if(n == 134)printf("1 14 22
");
if(n == 135)printf("1 10 26
");
if(n == 136)printf("1 14 22
");
if(n == 137)printf("1 8 27
");
if(n == 138)printf("1 8 27
");
if(n == 139)printf("1 14 22
");
if(n == 140)printf("1 8 27
");
if(n == 141)printf("1 8 27
");
if(n == 142)printf("1 10 26
");
if(n == 143)printf("1 8 27
");
if(n == 144)printf("1 8 27
");
if(n == 145)printf("1 8 27
");
if(n == 146)printf("1 8 27
");
if(n == 147)printf("1 8 27
");
if(n == 148)printf("1 8 27
");
if(n == 149)printf("1 8 27
");
if(n == 150)printf("1 8 27
");
if(n == 151)printf("1 8 27
");
if(n == 152)printf("1 8 27
");
if(n == 153)printf("1 9 30
");
if(n == 154)printf("1 9 30
");
if(n == 155)printf("1 9 30
");
if(n == 156)printf("1 9 30
");
if(n == 157)printf("1 9 30
");
if(n == 158)printf("1 9 30
");
if(n == 159)printf("1 9 30
");
if(n == 160)printf("1 9 30
");
if(n == 161)printf("1 9 30
");
if(n == 162)printf("1 9 30
");
if(n == 163)printf("1 9 30
");
if(n == 164)printf("1 9 30
");
if(n == 165)printf("1 9 30
");
if(n == 166)printf("1 9 30
");
if(n == 167)printf("1 9 30
");
if(n == 168)printf("1 9 30
");
if(n == 169)printf("1 9 30
");
if(n == 170)printf("1 9 30
");
if(n == 171)printf("1 9 30
");
if(n == 172)printf("1 12 31
");
if(n == 173)printf("1 12 31
");
if(n == 174)printf("1 12 31
");
if(n == 175)printf("1 12 31
");
if(n == 176)printf("1 10 34
");
if(n == 177)printf("1 10 34
");
if(n == 178)printf("1 10 34
");
if(n == 179)printf("1 10 33
");
if(n == 180)printf("1 10 34
");
if(n == 181)printf("1 10 34
");
if(n == 182)printf("1 10 34
");
if(n == 183)printf("1 10 34
");
if(n == 184)printf("1 10 34
");
if(n == 185)printf("1 10 34
");
if(n == 186)printf("1 10 34
");
if(n == 187)printf("1 10 34
");
if(n == 188)printf("1 12 31
");
if(n == 189)printf("1 12 31
");
if(n == 190)printf("1 12 31
");
if(n == 191)printf("1 12 31
");
if(n == 192)printf("1 12 31
");
if(n == 193)printf("1 12 31
");
if(n == 194)printf("1 12 31
");
if(n == 195)printf("1 12 31
");
if(n == 196)printf("1 12 31
");
if(n == 197)printf("1 17 27
");
if(n == 198)printf("1 12 31
");
if(n == 199)printf("1 12 31
");
if(n == 200)printf("1 12 31
");
}
return 0;
}// - xgtao -
D - 柱爷的恋爱
题意：
给出一个包含") ( ] ["的括号序列,可以选择括号删除,但是不能全部删除,问有多少种方式让其成为合法的括号序列(%1000000007),
合法的括号序列定义如下:
- 如果S是合法序列,那(S)和[S]也是合法序列。
- 如果A和B都是合法序列,那么AB也是合法序列。
- (), [], (()), ([]), ()[], ()[()]。
题解：
0.因为如果A,B是合法的那么AB也是合法的,所以这是区间dp。
1.定义状态dp[i][j]表示在i~j这个区间内的合法方案数目。
2.状态转移种,括号面临两种决策,删还是不删。
3.如果删除当前的一个括号dp[i][j] = dp[i+1][j]。
4.如果不删除,但必须满足后面有一个括号能够和它匹配,如果i&k匹配那么[i+1,k-1]要合法,[k+1,j]也要合法 dp[i][j] += dp[i+1][k-1]*dp[k+1][j]。
5.因为计算的是dp[0][n-1]包含了把括号全部删除的情况,所以最后要+1。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
#define ll long long
const int N = 500;
ll f[N][N];
char bracket[N];
int n,vis[N][N];
bool flag(int l,int r){
if(bracket[l] == '(' && bracket[r] == ')')return true;
if(bracket[l] == '[' && bracket[r] == ']')return true;
return false;
}
ll dp(int l,int r){
if(vis[l][r])return f[l][r];
vis[l][r] = 1;
if(l >= r)return f[l][r] = 1;
f[l][r] = dp(l+1,r)%mod;
for(int k = l;k <= r;++k){
if(!flag(l,k))continue;
f[l][r] = (f[l][r]+dp(l+1,k-1)*dp(k+1,r))%mod;
}
return f[l][r]%mod;
}
int main(){
scanf("%d",&n);
scanf("%s",bracket);
cout<<(dp(0,n-1)-1)%mod<<endl;
return 0;
}// - xgtao -
E - 柱爷与远古法阵
题意：
有一排长度为n(<=300)的格子,从1开始走到n,有一个骰子(1~6),每次可以走骰子的点数那么多的步数,并且中途会有一些传送门,求走到n点的期望数。
题解：
0.定义状态dp[x]表示从x点走到n的期望步数。
1.状态转移有两种情况,这个点有还是没有传送门。
2.是有传送门:dp[x] = dp[x']
3.没有传送门并且x <= n-6:由全期望公式得到dp[x] = (dp[x+1]+dp[x+2]+dp[x+3]+dp[x+4]+dp[x+5]+dp[x+6])/6 + 1;
4.没有传送门并且x > n-6也就是面临越界的情况dp[x] = (dp[x]+dp[x]+dp[x+1]+...dp[n])/6 + 1;因为越界了之后可以选择不走,它就转移到了自己,。
5.边界就是dp[n] = 0。
6.这里有n个点可以列出n个式子,那么就是n元一次方程,用高斯消元就可以解出dp[1]。
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const long double eps = 1e-14;
const int N = 400;
int n,m,link[N],u,v;
long double Gau[N][N];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)link[i] = i;
for(int i = 1;i <= m;++i){
scanf("%d%d",&u,&v);link[u] = v;
}
for(int i = 1;i < n;++i){
Gau[i][i] = 6.0;
if(link[i] != i)Gau[i][link[i]] = -6.0;
else{
Gau[i][n+1] = 6.0;
for(int j = 1;j <= 6;++j){
if(i+j <= n)Gau[i][i+j] = -1.0;
else {
Gau[i][i] -= 1.0;
}
}
}
}
Gau[n][n] = 1.0;
Gau[n][n+1] = 0;
for(int i = 1;i <= n;++i){
int cur = i;
for(int j = i+1;j <= n;++j)if(fabs(Gau[j][i])>eps)cur = j;
if(fabs(Gau[cur][i])>eps){
for(int j = i;j <= n+1;++j)swap(Gau[i][j],Gau[cur][j]);
for(int j = i+1;j <= n;++j){
if(fabs(Gau[j][i])<=eps)continue;
long double coe = Gau[j][i]/Gau[i][i];
for(int k = i;k <= n+1;++k){
Gau[j][k] -= Gau[i][k]*coe;
}
}
}
}
for(int i = n;i >= 1;--i){
for(int j = i+1;j <= n;++j){
if(fabs(Gau[i][j])<=eps)continue;
Gau[i][n+1] -= Gau[i][j]*Gau[j][n+1];
}
if(fabs(Gau[i][i])<=eps && fabs(Gau[i][n+1])>eps){
printf("-1
");
return 0;
}
Gau[i][n+1] /= Gau[i][i];
}
printf("%.10lf
",(double)Gau[1][n+1]);
return 0;
}// - xgtao -
F - 柱爷与三叉戟不得不说的故事
题意：
柱爷要修复三叉戟要15种元素,有两种方式,方式一：分别给出获得每一种元素的代价,方式二：分别给出获得一套元素的代价,要求一种元素不能重复获得,求最小代价。
题解：
0.数据范围是15,考虑状态压缩。
1.定义状态dp[S]表示获得S这个集合的元素的代价的最小值。
2.S是由其子集转移而来,状态转移dp[S] = min{dp[S0]+dp[S0^S]}。
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int dp[400010];
int main(){
memset(dp,127,sizeof(dp));
for(int i = 0;i < 15;++i)scanf("%d",&dp[(1<<i)]);
scanf("%d",&n);
for(int i = 0;i < n;++i){
int m,x,set = 0;
scanf("%d",&m);
for(int j = 1;j <= m;++j){
scanf("%d",&x),set |= (1<<(x-1));
}
scanf("%d",&x);
dp[set] = min(dp[set],x);
}
int all = (1<<15); dp[0] = 0;
for(int S = 0;S < all;++S){
for(int S0 = S;S0;S0 = (S0-1)&S)dp[S] = min(dp[S],dp[S0]+dp[S0^S]);
}
printf("%d
",dp[all-1]);
return 0;
}//- xgtao -
G - 柱爷与三叉戟
题意：
给出一个数n(<=10^500),定义函数F(x)表示x转化成二进制后1的个数,求满足1<=i<j<=n && F(i)>F(j)的对数。
题解：
0.首先考虑最原始最暴力的解法,从1开始枚举i,从i+1开始枚举j,再计算F(i)和F(j),如果F(i)>F(j)那么答案+1,但是发现F(x)计算多次,就发现可以记忆化,那么就考虑数位dp。
1.首先把n转成2进制数。
2.从高位开始枚举两个数i,j,始终保持i<j,并且记录F(i)与F(j)的差值,到了最后一位如果差值>0,就返回1。
3.状态定义：dp[pos][ch][lia][lib][lic]表示从高位考虑到pos位F(i)与F(j)之差为ch的个数,lia是枚举i的限制条件,lib是枚举j的限制条件,lic表示i是否小于j。
4.因为差值在某一位置可能为负数为了防止dp下标为负数,所以一开始dfs差值为N(N为二进制10^500的位数)。
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1667;
const int mod = 1000000007;
string str;
int dp[N+10][N*2+10][2][2][2];
string BigINt(string x){
string ret = "";
string c = "2333";
while(c.length()){
c = "";
char ch;
int i = 0;
while(i < x.length()){
ch = x[i]-'0';
if(ch>=2)c += static_cast<char>(ch/2+'0');
else if(c.length())c += '0';
if(ch%2 == 1 && i < x.length()-1)x[i+1] += 10;
++i;
}
ret = ret+static_cast<char>(ch%2+'0');
x = c;
}
return ret;
}
int dfs(int pos,int ch,bool lia,bool lib,bool lic){
if(pos == str.length())return (lic == 1 && ch > N);
if(dp[pos][ch][lia][lib][lic] != -1)return dp[pos][ch][lia][lib][lic];
int &ret = dp[pos][ch][lia][lib][lic] = 0;
int end1 = lia ? str[pos]-'0' : 1;
int end2 = lib ? str[pos]-'0' : 1;
for(int i = 0;i <= end1;++i){
for(int j = 0;j <= end2;++j){
if(!lic && i > j)continue;
ret = (ret+dfs(pos+1,ch+(i==1)-(j==1),lia&&i==end1,lib&&j==end2,lic||i<j))%mod;
}
}
return ret%mod;
}
int main(){
cin>>str;
str = BigINt(str);
reverse(str.begin(),str.end());
memset(dp,-1,sizeof(dp));
printf("%d
",dfs(0,N,1,1,0));
return 0;
}// - xgtao -
H - 柱爷大战滑稽王
题意：
给出两个长度为n(<=1000000)序列A,B,(|Ai,Bi|<=10^9),保证同一序列数字不重复,求这两个序列的最长公共子序列。
题解：
0.每个数字数据范围太大需要离散。
1.把A中的每一个数字出现的位置记录下来,在B中把A中出现的数的位置按B排好。
也就是说 A: 1 5 6 9 4
B： 1 6 9 4 5 对应关系也就是：1在A中的位置是1，6在A中的位置是3，9在A中的位置是4，4在A中的位置是5，5在A中的位置是2。
对应得到 C: 1 3 4 5 2
2.问题转化为求C得LIS，LIS的O(nlogn),就是在一个序列中不断替换第一个大于等于当前的数,因为这样序列就更有延展性,答案保证不会差,但是并不一定是这一个序列,但是长度一定相同的。
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000001;
int n,m,x,cnt,ans,p[N],g[N],dp[N],id[N],c[N],ncnt,hase[N];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i){
scanf("%d",&c[i]);
hase[++ncnt] = c[i];
}
sort(hase+1,hase+ncnt+1);
for(int i = 1;i <= n;++i){
int l = lower_bound(hase+1,hase+1+ncnt,c[i])-hase;
id[l] = i;
}
for(int i = 1;i <= m;++i){
scanf("%d",&x);
int l = lower_bound(hase+1,hase+1+ncnt,x)-hase;
if(hase[l] != x)continue;
p[++cnt] = id[l];
}
memset(g,127,sizeof(g));
for(int i = 1;i <= cnt;++i){
int k = lower_bound(g+1,g+cnt+1,p[i])-g;
dp[i] = k;
g[k] = p[i];
ans = max(ans,dp[i]);
}
cout<<ans+1<<endl;
return 0;
}// - xgtao -
I - 柱爷抢银行
题意：
给出n*m的矩阵,表示aij表示i行j列的金钱数目,如果aij<0,如果选择了这点会损失abs(aij)，如果aij>0,就可以直接得到钱,柱爷因为实力很强所以要走一个联通块,柱爷不是个退缩的人！来了就要抢。
题解：
0.状态定义：dpl[i][j]表示在i行j列向左走能够得到的最大值,dpr[i][j]表示在i行j列向右走的最大值，dpu[i][k]表示链接(i,k)这个点的上面的联通块的最大值。
1.状态转移：dpl,dpr不难写出dpl[i][j+1] = max{dpl[i][j]+mat[i][j+1]} dpr[i][j-1] = max{dpr[i][j]+mat[i][j-1]}
2.状态转移：dpu有两种决策
①:dpu[i+1][j] = max{dpu[i][k]+sum[j]-sum[k-1]+dpr[i][j+1]+dpl[i][k-1]} = max{dpu[i][k]-sum[k-1]+dpl[i][k-1]}+sum[j]+dpr[i][j+1]}
也就是当(k<=j)时维护max{dpu[i][k]-sum[k-1]+dpl[i][k-1]}
②:dpu[i+1][j] = max{dpu[i][k]+sum[k]-sum[j-1]+dpr[i][k+1]+dpl[i][j-1]} = max{dpu[i][k]+sum[k]+dpr[i][k+1]}-sum[j-1]+dpl[i][j-1]}
也就是当(k>=j)时维护max{dpu[i][k]+sum[k]+dpr[i][k+1]}
3.答案也就是max{dpu[i+1][j],dpl[i][j-1]+mat[i][j]+dp[i][j+1]}
4.如果为空集的话就特判一下。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1010;
const ll inf = 1e20;
int n,m,flag;
ll sum[N][N],dpl[N][N],dpr[N][N],dpu[N][N],maxg,mat[N][N],maxp,ret;
int main(){
scanf("%d%d",&n,&m);
maxp = ret = maxg = -inf;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
cin>>mat[i][j];
if(!flag && mat[i][j]>0)flag = 1;
maxg = max(maxg,mat[i][j]);
sum[i][j] = sum[i][j-1]+mat[i][j];
}
}
for(int i = 1;i <= n;++i){
for(int k = 1;k <= m;++k){
dpl[i][k] = max(dpl[i][k],mat[i][k]);
dpl[i][k+1] = max(dpl[i][k+1],dpl[i][k]+mat[i][k+1]);
}
for(int k = m;k >= 1;--k){
dpr[i][k] = max(dpr[i][k],mat[i][k]);
dpr[i][k-1] = max(dpr[i][k-1],dpr[i][k]+mat[i][k-1]);
}
maxp = -inf;
for(int k = 1;k <= m;++k){
maxp = max(maxp,dpu[i][k]-sum[i][k-1]+dpl[i][k-1]);
dpu[i+1][k] = max(dpu[i+1][k],maxp+sum[i][k]+dpr[i][k+1]);
ret = max(ret,dpl[i][k-1]+mat[i][k]+dpr[i][k+1]);
ret = max(ret,dpu[i+1][k]);
}
maxp = -inf;
for(int k = m;k >= 1;--k){
maxp = max(maxp,dpu[i][k]+sum[i][k]+dpr[i][k+1]);
dpu[i+1][k] = max(dpu[i+1][k],maxp-sum[i][k-1]+dpl[i][k-1]);
ret = max(ret,dpl[i][k-1]+mat[i][k]+dpr[i][k+1]);
ret = max(ret,dpu[i+1][k]);
}
}
if(!flag && ret == 0)ret = maxg;
cout<<ret<<endl;
return 0;
} // - xgtao -
J - 柱爷抢银行II
题意：
有n(<=1000000)个银行是按照顺时针的圈排布,给出在每个银行可以抢多少钱,柱爷决定选择不超过长度为k(<=1000000)的区间里面抢钱,求最多能抢多少？柱爷不是个退缩的人！来了就要抢！
题解：
0.既然是环,那么就需要断环为链。
1.定义状态dp[i]表示在i点之前长度不超过k的区间最大和。
2.状态转移很容易想到dp[i] = max{dp[i-1],sum[i]-sum[j-1]}(i-k+1<=j<=i) 复杂度为O(n*k),这个复杂度伤不起。
3.就用单调递增队列维护sum[j-1],单调队列的头就是最优sum的下标。注意维护的下标是j-1
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4000000;
int n,k,a[N],sum[N],dp[N],ansl,ansr;
class singlequeue{
protected:
int q[N],head,tail;
public:
void pop_back(){--tail;}
void pop_front(){++head;}
int back(){return q[tail];}
int front(){return q[head];}
int size(){return tail-head+1;}
void push_back(int x){q[++tail] = x;}
void init(){head = 0,tail = -1;}
bool empty(){return tail-head+1>0 ? 0 : 1;}
singlequeue(){init();}
}sq;
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i){
scanf("%d",&a[i]),a[n+i] = a[i];
}
for(int i = 1;i <= 2*n;++i){
sum[i] = sum[i-1]+a[i];
}
sq.init();ansl = ansr = 1;
sq.push_back(1); dp[1] = sum[1];
for(int i = 2;i <= 2*n;++i){
while(!sq.empty() && sq.front() < i-k) sq.pop_front();
if(dp[i-1] < sum[i]-sum[sq.front()]){
dp[i] = sum[i]-sum[sq.front()];
ansl = sq.front() + 1;
ansr = i;
}
else dp[i] = dp[i-1];
while(!sq.empty() && sum[i] < sum[sq.back()])sq.pop_back();
sq.push_back(i);
}
printf("%d %d %d
",dp[2*n],ansl>n?ansl-n:ansl,ansr>n?ansr-n:ansr);
return 0;
}// - xgtao -
K - 柱爷抢银行III
题意：
给出一棵树,节点数<=500,每一个节点代表一个银行,柱爷抢银行太熟练所以抢银行不会消耗精力,但是柱爷从一个银行到另外一个银行会消耗精力,有q个询问,给出一开始柱爷的精力,问柱爷从0号点出发最多能抢几家银行？
题解：
0.不难看出这是一个树形dp,定义状态dp[u][i][0/1]表示在根节点为u的子树中抢i家银行并且当前是否在i这个节点最小的精力消耗。
1.状态转移:dp[u][i+k][0] = max{dp[u][i][1]+dp[v][k][1]+w,dp[u][i][0]+dp[v][k][1]+2*w,dp[u][i][1]+dp[v][k][0]+w}
dp[u][i+k][1] = max{dp[u][i][1]+dp[v][k][1]+2*w}
2.最后只需倒序枚举节点数,找到第一个小于等于原始精力的min{dp[0][i][1],dp[0][i][0]}，输出i。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
struct edge{
int v,w;
edge *nxt;
}*head[N],*cur,Edge[N*2];
int dp[N][N][2],size[N],n,u,v,w,q,x;
void addedge(int u,int v,int w){
cur->v = v;
cur->w = w;
cur->nxt = head[u];
head[u] = cur++;
}
int dfs(int u,int fa){
dp[u][1][1] = 0;
size[u] = 1;
for(edge *it = head[u];it;it = it->nxt){
int v = it->v;
if(v == fa)continue;
size[v] = dfs(v,u);
for(int i = size[u];i >= 1;--i){
for(int k = size[v];k >= 1;--k){
dp[u][i+k][0] = min(dp[u][i+k][0],dp[u][i][0]+dp[v][k][1]+2*it->w);
dp[u][i+k][0] = min(dp[u][i+k][0],dp[u][i][1]+dp[v][k][0]+1*it->w);
dp[u][i+k][0] = min(dp[u][i+k][0],dp[u][i][1]+dp[v][k][1]+1*it->w);
dp[u][i+k][1] = min(dp[u][i+k][1],dp[u][i][1]+dp[v][k][1]+2*it->w);
}
}
size[u] += size[v];
}
return size[u];
}
int main(){
cur = Edge;
scanf("%d",&n);
for(int i = 0;i < n-1;++i){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
scanf("%d",&q);
memset(dp,127,sizeof(dp));
dfs(0,-1);
while(q--){
scanf("%d",&x);
for(int i = n;i >= 1;--i){
if(min(dp[0][i][0],dp[0][i][1])<=x){
printf("%d
",i);
break;
}
}
}
return 0;
}// - xgtao -
L - 柱爷抢银行MkⅣ
题意：
一条街上有n(<=100000)个银行,对于第i个银行位置是x[i](<=109),钱是w[i](<=109),并且对于i号银行,只有位置比i小y[i]以内的银行才能到i。柱爷不是个退缩的人！来了就要抢！
题解：
0.因为位置的数据范围太大,需要离散,再把银行按照位置从小到大排序。
1.定义状态dp[i]表示到达i号银行所得的最多的钱数。
2.状态转移dp[i] = max{dp[j]+w[i]}(i-y[i]<=j<i)复杂度为O(n*n)所以需要优化。
3.用线段树维护区间[i-y[i],i]这个区间里的极大值,再单点修改i点的极大值
4.转台转移即为dp[i] = query(1,1,n,i-y[i],i)+w[i],修改即为update(1,1,n,i,dp[i])
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 100010;
struct gg{ll v;int x,y;}bank[N];
int hase[N],cnt;
ll maxi[N<<2],n,dp[N];
ll query(int k,int l,int r,int L,int R){
if(L <= l && R >= r)return maxi[k];
int mid = (l+r)>>1;
ll ret = 0;
if(L <= mid)ret = max(ret,query(k<<1,l,mid,L,R));
if(R > mid)ret = max(ret,query(k<<1|1,mid+1,r,L,R));
return ret;
}
void update(int k,int l,int r,int x,ll w){
if(l == r){
maxi[k] = max(maxi[k],w);
return;
}
int mid = (l+r)>>1;
if(x <= mid)update(k<<1,l,mid,x,w);
else if(x > mid)update(k<<1|1,mid+1,r,x,w);
maxi[k] = max(maxi[k<<1],maxi[k<<1|1]);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d%d%d",&bank[i].x,&bank[i].v,&bank[i].y);
hase[++cnt] = bank[i].x;
}
sort(hase+1,hase+1+cnt);
cnt = unique(hase+1,hase+cnt+1)-hase-1;
for(int i = 1;i <= n;++i){
int r = lower_bound(hase+1,hase+1+cnt,bank[i].x)-hase;
int l = lower_bound(hase+1,hase+1+cnt,bank[i].x-bank[i].y)-hase;
dp[i] = bank[i].v+query(1,1,cnt,l,r);
update(1,1,cnt,r,dp[i]);
}
ll ans = 0;
for(int i = 1;i <= n;++i)ans = max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}// - xgtao -
M - 柱爷抢银行欢庆5.1special
题意：
给出一个n*m(<=500)的方阵,方阵中的每个格子都有一家银行，柱爷抢这家银行能得到aij的钱，当aij<0柱爷会损失的钱。他决定要抢的银行要形成k阶顺时针螺旋状，其中k为≥3的任意奇数。下面是k=3,5,7的图形，其中黑色方块是柱爷要抢钱的银行。求最多抢的钱数，柱爷不是个退缩的人！来了就要抢！
题解：
0.很容易观察出pic3的白色部分和pic2的黑色部分形状是一样的,只不过多了那一小块。
1.定义状态：dp[i][j][k]表示以(i,j)这个点为左上角并且当前是第k阶的黑色部分的和,但是500*500*500会爆,所以要滚动~
2.状态转移：dp[i][j][x] = gs(i,j,i+k-1,j+k-1)-dp[i+1][j+1][x^1]-mat[i+1][j] (k = 3;k <= min(n,m);k+=2)
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int sum[N][N],n,m,mat[N][N],dp[N][N][2];
int gs(int x,int y,int i,int j){
return sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1];
}
int main(){
scanf("%d%d",&n,&m);
int x = 1;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
scanf("%d",&mat[i][j]);
dp[i][j][x] = mat[i][j];
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i][j];
}
}
int ans = -1e9;
for(int k = 3;k <= min(m,n);k+=2){
x ^= 1;
for(int i = 1;i+k-1 <= n;++i){
for(int j = 1;j+k-1 <= m;++j){
dp[i][j][x] = gs(i,j,i+k-1,j+k-1)-dp[i+1][j+1][x^1]-mat[i+1][j];
ans = max(ans,dp[i][j][x]);
}
}
}
cout<<ans<<endl;
return 0;
}// - xgtao -
N - 柱爷与子序列
题意：
给出一个长度为n(<=100000)的序列A,Ai<=10^9,求出一共有多少组完美子序列(长度>=2,下标呈升序,相邻两数差的绝对值小于一个数k),对1000000009取模。
题解：
0.数据太大，肯定需要离散。
1.状态定义：dp[i]表示以A[i]结尾的完美子序列的个数。
2.状态转移：dp[i] += dp[j](abs(A[j]-A[i]) <= k && 1 <= j < i),复杂度O(n^2)所以要优化。
3.用树状数组离散后的序列,以值为下标,那么能够与A[i]对接的就是A[i]-k ~ A[i]+k 这段区间,树状数组维护的是一个以1~某个值结尾前缀和。
4.状态转移：dp[x] += query(x+k)-query(x-k-1), update(x,dp[x]+1);
5.最后把dp[]求和。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
const int mod = 1000000009;
#define lowbit(i) i&-i
#define ll long long
ll c[N],ret;
int a[N],cnt,hase[N],n,k;
ll query(int x){
ll ret = 0;
for(int i = x;i >= 1;i -= lowbit(i)){
ret = (ret+c[i])%mod;
ret = (ret+mod)%mod;
}
return ret;
}
void update(int x,ll p){
for(int i = x;i <= N;i += lowbit(i)){
c[i] = (c[i]+p)%mod;
c[i] = (c[i]+mod)%mod;
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i){
cin>>a[i];
hase[++cnt] = a[i];
}
sort(hase+1,hase+cnt+1);
cnt = unique(hase+1,hase+cnt+1)-hase-1;
for(int i = 1;i <= n;++i){
int x = lower_bound(hase+1,hase+1+cnt,a[i])-hase;
int l = lower_bound(hase+1,hase+1+cnt,a[i]-k)-hase;
int r = upper_bound(hase+1,hase+1+cnt,a[i]+k)-hase;--r;
ll c = query(r)-query(l-1);//c可能为负数因为query(r)被%,query(l-1)还没有被%
ret = (ret+c)%mod;
ret = (ret+mod)%mod;
update(x,c+1);
}
cout<<ret<<endl;
return 0;
}// - xgtao -
O - 柱爷很忙
题意：
给出n(n<=1000)件事情的类型ai和重要性bi(<=7),事情可以推后,但是一件事情为K,并且K>i+b[i]则k就不能放在i之前做完,如果要做事情类型为i，前一件做的事情为j,那么要花费的时间为(a[i]|a[j])-(a[i]&a[j]),求做完事情的最短时间。
题解：
0.b的数据范围才7,考虑状态压缩。
1.定义状态：dp[i][S][d]第一维表示以第i件事情结尾,第二维表示以i结尾的最后8件事情的完成情况为S,第三维d表示上一件做的事情离i的距离,dp表示最短的时间
2.状态转移：有两种决策：
①对于以i结尾的8件事情先不慌,往后推,dp[i+1][S^(1<<7)<<1][min(d+1,16)] = min{dp[i][S][d]};(条件是以i结尾的8件事情中最早的那一件事情先做完)
②对于以i结尾的8件事情要做,dp[i][S|(1<<k)][k] = min{dp[i][S][l]+((d==16)?a[i-k]:(a[i-k]|a[i-d])-(a[i-k]&a[i-d])};(条件是离i的距离为k的那件事情没有做过,并且要把不能再拖的事情做了)
(注意d最多为15,d == 16是因为特判第一件事情)。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int all = 1<<8;
const int inf = 0x7f7f7f7f;
const int N = 1616;
int n,a[N],b[N],dp[N][all][21];
int main(){
scanf("%d",&n);
memset(dp,0x7f,sizeof(dp));
for(int i = 1;i <= n;++i)cin>>a[i]>>b[i];
dp[0][all-1][16] = 0;
for(int i = 0;i <= n;++i)
for(int S = 0;S < all;++S)
for(int d = 0;d <= 16;++d)
if(dp[i][S][d] != inf){
int p = min(i,8),putoff = inf;
for(int k = p-1;k >= 0;--k){
if( ((S>>k)&1) == 0 )putoff = min(putoff,i-k+b[i-k]);
}
if( ((S>>7)&1) == 1){
dp[i+1][(S^(1<<7))<<1][min(d+1,16)] = min(dp[i+1][(S^(1<<7))<<1][min(d+1,16)],dp[i][S][d]);
}
for(int k = p-1;k >= 0 && i<=putoff+k;--k){
if(((S>>k)&1) == 0){
dp[i][S|(1<<k)][k] = min(dp[i][S|(1<<k)][k],dp[i][S][d]+((d==16)?a[i-k]:(a[i-k]|a[i-d])-(a[i-k]&a[i-d])));
}
}
}
int ret = inf;
for(int i = 0;i <= 16;++i)ret = min(ret,dp[n][all-1][i]);
cout<<ret<<endl;
return 0;
}// - xgtao -
P - 柱爷的矩阵
题意：
给出矩阵的行数n(<=1000),给出每一行第一个数a[i]，再给出每一行的b[i],a[i][j+1] = a[i][j]-b[i],在每一行每一列取至多一个数,求取出的数和最大。
题解：
0.对于要去第i行,第j行的数字并且b[i]>b[j]要先考虑第i行的那个数字,所以要按照b从大到小排序。
1.状态定义：dp[i][j][0/1],dp[i][j][0]表示不一定选了(i,j)这个位置的数字,也就是说所选的数字在k1(k1<=i)行的k2列(k2<=j)处,dp[i][j][1]必定选(i,j)这个位置的数字时的最大值。
2.状态转移：dp[i][j][1] = dp[i-1][j-1][0]+max(0,a[i]-(j-1)*b[i])
dp[i][j][0] = max{dp[i-1][j][0],dp[i][j-1],dp[i][j][1]}
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N][2],n,m;
struct node{
int a,b;
bool operator < (const node &rhs)const{
return b > rhs.b;
}
}x[N];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)scanf("%d",&x[i].a);
for(int i = 1;i <= n;++i)scanf("%d",&x[i].b);
sort(x+1,x+n+1);
for(int j = 1;j <= m;++j){
for(int i = 1;i <= n;++i){
dp[i][j][1] = dp[i-1][j-1][0]+max(0,x[i].a-(j-1)*x[i].b);
dp[i][j][0] = max(dp[i-1][j][0],dp[i][j-1][0]);
dp[i][j][0] = max(dp[i][j][0],dp[i][j][1]);
}
}
cout<<dp[n][m][0]<<endl;
return 0;
}// - xgtao -
Q - 柱爷的宝藏
题意：
给出一个长度为n(<=500000)的序列,把这个序列分成任意多个区间,如果某个区间有{a[x]，a[x+1]，...a[y]},那么这个区间的权值为(a[x]+a[x+1]+...a[y])^2+m,怎么划分使得整个序列的区间权值和最小，求最小权值。
题解：
0.定义状态：dp[i]表示前i个数的组成序列的所有区间的权值和。
1.状态转移：dp[i] = min{dp[j]+(sum[i]-sum[j])^2+m}(1<=j<i)复杂度为O(n^2)超时！
2.斜率优化！！
①假设k<j<i如果j比k优,那么dp[j]+(sum[i]-sum[j])^2+m<dp[k]+(sum[i]-sum[k])^2+m化简后得到式子[(dp[j]+sum[j]^2)-(dp[k]+sum[k]^2)]/(2*sum[j]-2*sum[k])<sum[i],令dp[]+sum[]^2为y[]，令2*sum[x]为x[],那么将x[],y[]带入原式,则g[j,k] = (y[j]-y[k])/(x[j]-x[k])<sum[i]。
②那么反过来如果g[j,k]<sum[i],就可以得到j一定比k优，再反过来g[j,k]>sum[i]那么k一定比j优,如果g[j,k] = sum[i]那么k一定不会比j差
③从左到右a<b<c<i,如果g[b,a]>=g[c,b],那么b永远不可能为最优解,证明需要分类讨论
假设sum[i]>=g[b,a]>=g[c,b]这种情况下c优于b优于a或者b一起优，但是我们也可以不选b啊 
假设g[b,a]>=sum[i]>=g[b,c]这种情况是a优于b优于c或者b一起优，但是我们也可以不选b啊
假设g[b,a]>=g[c,b]>=sum[i]这种情况是a优于b优于c或者b一起优，但是我们也可以不选b啊
总而言之每一种情况下b都不可能成为最优的。
④排除了g[b,a]>g[c,b]这种情况之后,就只剩下g[b,a]<=g[c,b]的情况,那么斜率整个就成一个单调递增的了。
⑤用一个单调队列来维护斜率。
⑥入队的时候如果队列中已经有a,b,c,d,e五个元素了,现在f需要进队但是如果g[e,d]>=g[f,e]那么e就出队,直到满足单调递增为止
⑦求解的时候如果队列中已经有a,b,c,d,e五个元素了,如果g[b,a]<=sum[i]a就排除,a就出队,直到找到一个g[head+1,head]>=sum[i]为止
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define square(i) ((i)*(i))
const int N = 500010;
ll dp[N],sum[N],n,m,x,sq[N];
ll deltay(ll i,ll j){
return dp[i]-dp[j]+square(sum[i])-square(sum[j]);
}
ll deltax(ll i,ll j){
return sum[i]-sum[j] <<1;
}
int main(){
cin>>n>>m;
for(int i = 1;i <= n;++i){
cin>>x;
sum[i] = sum[i-1]+x;
}
int head = 0,tail = -1;
for(int i = 1;i <= n;++i){
while(tail-head+1>0 && deltay(sq[head+1],sq[head])<=deltax(sq[head+1],sq[head])*sum[i])++head;
dp[i] = dp[sq[head]]+square(sum[i]-sum[sq[head]])+m;
while(tail-head+1>0 &&
deltay(i,sq[tail])*deltax(sq[tail],sq[tail-1])<=deltay(sq[tail],sq[tail-1])*deltax(i,sq[tail])
)--tail;
sq[++tail] = i;
}
cout<<dp[n]<<endl;
return 0;
}// - xgtao -
R - 柱爷把妹（吃惊高清重制版）
题意：
柱爷通过PY交易,知道了接下来n天的股市行情,第i天买入卖出的的价格为Pi,每天柱爷可以买卖或者不动,但是买卖一次会交F的手续费,买之前扣,卖之后扣,柱爷也有一定的本金m,求最大收益。
题解：
0.定义状态：dp[i][0/1]，dp[i][0]表示第i天不做任何操作拥有的钱,dp[i][1]表示第i天操作后有的钱
1.
①假设p[a]<p[b]<p[c]。
②分析a->b(a天买b天卖)moneya-b = (m-F)/p[a]*p[b]-F+(m-F)%p[a]
③分析a->c(a天买c天卖)moneya-c = (m-F)/p[a]*p[c]-F+(m-F)%p[a]
④分析a->b->c moneya-b-c = (moneya-b+F)/p[b]*p[c]-F+(moneya-b+F)%p[b] = {(m-F)/p[a]*p[b]+(m-F)%p[a]}/p[b]*p[c]-F+{(m-F)/p[a]*p[b]+(m-F)%p[a]}%p[b]
因为p[a]<p[b]所以(m-F)%p[a]/p[b]为0,又因为(m-F)/p[a]*p[b]%p[b]等于0，所以moneya-c = (m-F)/p[a]*p[c]-F+(m-F)%p[a];
⑤所以得到结论moneya-b-c = moneya-c;
2.状态转移:
①dp[nxt[i]][1] = max{(dp[i][0]-F)/p[i]*p[nxt[i]]-F+(dp[[i][0]-F)%p[i],(dp[i][1]+F)/p[i]*p[nxt[i]]-F+(dp[i][1]-F)%p[i]}(p[nxt[i]]>p[i])
②dp[i+1][0] = max{dp[i][0],dp[i][1]}
③dp[nxt[i]][0] = max{dp[i][0],dp[i][1]}
3.预处理出nxt[i]就解决问题了。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 100010;
ll dp[N][2];
int Stack[N],p[N],nxt[N],n,m,f;
int main(){
cin>>n>>m>>f;
for(int i = 1;i <= n;++i)cin>>p[i];
int top = 0;Stack[top] = n;
for (int i = n; i; --i){
while (top && p[i] >= p[Stack[top]])--top;
nxt[i] = top?Stack[top]:i;
Stack[++top] = i;
}
memset(dp,128,sizeof(dp));
dp[1][0] = m;ll tmp,ans = 0;
for(int i = 1;i <= n;++i){
ans = max(ans,max(dp[i][0],dp[i][1]));
dp[i+1][0] = max(dp[i+1][0],max(dp[i][0],dp[i][1]));
dp[nxt[i]][0] = max(dp[nxt[i]][0],max(dp[i][0],dp[i][1]));
if(nxt[i] <= i)continue;
tmp = dp[i][0]-f;
if(tmp > 0)dp[nxt[i]][1] = max(dp[nxt[i]][1],tmp/p[i]*p[nxt[i]]+tmp%p[i]-f);
tmp = dp[i][1]+f;
if(tmp > 0)dp[nxt[i]][1] = max(dp[nxt[i]][1],tmp/p[i]*p[nxt[i]]+tmp%p[i]-f);
}
cout<<ans<<endl;
return 0;
}// - xgtao -