A - Function Run Fun

A - Function Run Fun

思路：
-记忆化搜索

代码如下：

#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 30, M = 1010;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp[N][N][N];

int w(int a, int b, int c)
{
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if(a > 20 || b > 20 || c > 20) return w(20, 20, 20);
    
    int &v = dp[a][b][c];
    
    if(v != -1) return v;
    else if(a < b && b < c) v =  w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else v = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);    
    
    return v;
}   

signed main()
{
    //fast;
    //int T = 1;
    //cin >> T;
    
    memset(dp, -1, sizeof dp);
    
    int a, b, c;
    while(cin >> a >> b >> c, ( (a != -1) || (b != -1) || (c != -1) ))
    // 也可如此特判：while(cin >> a >> b >> c, ~a || ~b || ~c)
        printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    
    return 0;
}
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

---

B - 阿克曼函数

B - 阿克曼函数

思路：

• 记忆化搜索

阿克曼函数:

简介： 可以在极短时间内将小数编程大数，因此记忆化搜索第二维 $n$ 及其不好确认，因此先找规律，确认边界

阿克曼函数为 $(2,2)$ 时，举例：

规律如下：

int akm(int m,int n)
{
    if(m == 0) return n+1;
    if(m == 1) return n+2;
    if(m == 2) return 2*n+3;
    if(m == 3) return (1<<(n+3))-3;
}
1
2
3
4
5
6
7

可知递归边界的 $n$ 最大为 1 << (n + 3)

记忆化搜索代码如下:

#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 5, M = 1 << 19;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int dp[N][M];

int akm(int m, int n)
{
    int &v = dp[m][n];
    
    if(v != -1) return v;
    else if(m == 0) v = n + 1;
    else if(m > 0 && n == 0) v = akm(m - 1, 1);
    else if(m > 0 && n > 0) v = akm(m - 1, akm(m, n - 1));  
    
    return v;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    cin >> m >> n;
    cout << akm(m, n) << endl;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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

---

C - Free Candies

C - Free Candies

思路：

• 记忆化搜索（直接搜会 $TLE$ )

代码解释：

• a[N][4]数组 表示 四个小桶里每个桶都有N个球
• dp[N][N][N][N]表示当前每个桶装到了第几个球，数据内容为最大的对数
• p[4]数组表示当前 第i个桶装到了第p[i]个球
• st[N * 4]数组表示该球上的数字是否在桶里，分类讨论

代码如下：

#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 60, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int p[4];
int a[N][4];
int dp[N][N][N][N];
bool st[N * 4];

int dfs(int cnt)
{
    int &v = dp[p[0]][p[1]][p[2]][p[3]];
    
    if(v != -1) return v;
    
    v = 0;
    if(cnt >= 5) return v;
    for (int i = 0; i < 4; i ++ )
    {
        if(p[i] >= n) continue;
        p[i] ++;
        
        if(st[a[p[i]][i]])
        {
            st[a[p[i]][i]] = false;
            v = max(v, dfs(cnt - 1) + 1);
            st[a[p[i]][i]] = true;
        }
        else
        {
            st[a[p[i]][i]] = true;
            v = max(v, dfs(cnt + 1));
            st[a[p[i]][i]] = false;
        }
        p[i] --;
    }
    
    return v;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    memset(st, 0, sizeof st);
    memset(p, 0, sizeof p);
    
    // 此处 i 从 1 开始，因为 p 数组初始化为 0 ，表示没有放入任何球
    // 若初始化 i 为 0 开始，则 p 数组初始化为 0，表示一开始就放入了 四个球
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < 4; j ++ )
            cin >> a[i][j];
            
    cout << dfs(0) << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(cin >> n, n)
        solve();
    
    return 0;
}
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

D - k-Tree

D - k-Tree

思路：

• 直接搜，记忆化搜索

代码如下：

#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 60, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, k, d;
int dp[110][2];

int dfs(int sum, bool flag)
{
    if(sum == 0)
    {
        if(flag) return 1;
        else return 0;
    }
    
    int &v = dp[sum][flag];
    if(v != -1) return v;
    
    v = 0;
    
    for (int i = 1; i <= k; i ++ )
    {
        if(sum >= i)
        {
            if(i >= d) flag = true;
            v += dfs(sum - i, flag);
            v %= mod;
        }
    }
    
    return v;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    
    cin >> n >> k >> d;
    
    cout << dfs(n, 0) << endl;
    // dfs(0, 0) 正搜，反搜均可
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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

浅浅改一下即可：

#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 60, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, k, d;
int dp[110][2];

int dfs(int sum, bool flag)
{
    if(sum > n) return 0;
    if(sum == n)
    {
        if(flag) return 1;
        else return 0;
    }
    
    int &v = dp[sum][flag];
    if(v != -1) return v;
    
    v = 0;
    
    for (int i = 1; i <= k; i ++ )
    {
        if(i >= d) flag = true;
        v += dfs(sum + i, flag);
        v %= mod;
    }
    
    return v;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    
    cin >> n >> k >> d;
    
    cout << dfs(0, 0) << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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

---

E - Cow Program

E - Cow Program

思路：

• dp[i][j]数组，表示dp[i][j]的该情况下i需要加上的数
• st[i][j]数组，表示 dp[i][j]是否用过
• 数组第二维，0表示第二步，1表示第三步

代码如下：

#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 2e6 + 10, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, k, d;
int a[N];
int dp[N][2];
bool st[N][2];

void dfs(int x, bool j)
{
    if (st[x][j]) return;
    
    st[x][j] = true;
    
    int y = x + a[x] * (j ? -1 : 1);
    
    if( y <= 0 || y > n)
    {
        dp[x][j] = a[x];
        return;
    }
    
    dfs(y, j ^ 1);
    
    if(dp[y][j ^ 1] != -1)
        dp[x][j] = dp[y][j ^ 1] + a[x];

    return;
}

void solve()
{
    memset(st, 0, sizeof st);
    memset(dp, -1, sizeof dp);
    
    cin >> n;
    
    for (int i = 2; i <= n; i ++ )
        cin >> a[i];
    
    st[1][0] = 1;
    st[1][1] = 1;
    dp[1][1] = 0;
    for (int i = 2; i <= n; i ++ )
        dfs(i, 1);
    
    for (int i = 2; i <= n; i ++ )
    {
        if(dp[i][1] != -1) dp[i][1] += i - 1;
        cout << dp[i][1] << endl;
    }
    
    return;
}

signed main()
{
    fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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

---

F - Cheapest Palindrome

F - Cheapest Palindrome

思路：

• 法一：区间 $DP$
• 法二：记忆化搜索

区间 $DP$：

状态表示：

• f[i][j]表示将第i个字符到第j字符变为回文串的最小代价
• 单字符f[i][i]和无字符f[i][i-1]本身就为回文串，最小代价为0

状态转移过程：

1. s[i] == s[j]时，并且f[i+1][j-1]为回文串，此时最小代价为0，即f[i][j] = f[i+1][j-1]
2. s[i] != s[j]时，此时分为四种情况 添头 添尾 删头 删尾
   如下所示：(w为执行此操作所需要的代价）
   • 添头：在i前添加一个字符s[j]，此时f[i][j-1]为回文串，状态转移为f[i][j] = f[i][j-1] + w
   • 添尾：在j前添加一个字符s[i]，此时f[i+1][j]为回文串，状态转移为f[i][j] = f[i+1][j] + w
   • 删头：删去i位置的字符s[i]，此时f[i+1][j]为回文串，状态转移为f[i][j] = f[i+1][j] + w
   • 删尾：删去j位置的字符s[j]，此时f[i][j-1]为回文串，状态转移为f[i][j] = f[i][j-1] + w
3. 其中 添头删尾 所依托的状态相同，可合并计算；添尾删头 所依托的状态相同，可合并计算

代码如下：

#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 2e3 + 10, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
char s[N];
int f[N][N];
map<char, int> cost;

void solve()
{
    memset(f, 0x3f, sizeof f);
    
    scanf("%d%d", &m, &n);
    scanf("%s", s + 1);
    char op[2];
    int x, y;
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%s%lld%lld", op, &x, &y);
        cost[op[0]] = min(x, y);
    }
    
    for (int i = 1; i <= n; i ++ )
        f[i][i] = f[i][i - 1] = 0;
    
    for (int len = 2; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1];
            f[l][r] = min(f[l][r], f[l + 1][r] + cost[s[l]]);
            f[l][r] = min(f[l][r], f[l][r - 1] + cost[s[r]]);
        }
    
    cout << f[1][n] << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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

记忆化搜索：

• 状态转移和 区间 $DP$ 差不多

代码如下：

#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 2e3+10, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
char s[N];
int dp[N][N];
map<char, int> cost;

int dfs(int l, int r)
{
    int &v = dp[l][r];
    
    if(v != -1) return v;
    
    if(l >= r) // 若：l + 1 == r && s[l] == s[r], 会出现 dfs(r, r - 1) 情况, 此时 l > r, 应该为 0
    {
        v = 0;
        return v;
    }
    
    if(s[l] == s[r]) v = dfs(l + 1, r - 1);
    else v = min(dfs(l + 1, r) + cost[s[l]], dfs(l, r - 1) + cost[s[r]]);
    
    return v;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    
    scanf("%lld %lld", &m, &n);
    scanf("%s", s + 1);
    char op[2];
    int x, y;
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%s%lld%lld", op, &x, &y);
        cost[op[0]] = min(x, y);
    }
    
    cout << dfs(1, n) << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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

---

G - 不正经消消乐

G - 不正经消消乐

思路：

• 记忆化搜索

具体步骤：

• 先将所有颜色相同的连续的块合在一起，产生idx个大块，并保存其颜色(box[idx].color)和长度(box[idx].len)
• 状态表示：
  1. 若：dp[i][j]：表示从大块 i到j这一段消除后能得到的最高分，则无法将位于不同位置的相同颜色的大块合并成较高的分数，只能合并已有的分数，所以此状态表示不可以
  2. 若：dp[i][j][len]：表示j的右边已经有一个长度为len的大块，大块i到j这一段和 len都消除后能得到的最高分，如此即可求出最大值，所求最大值即为dp[1][idx][0]
• 状态计算：
  1. 若计算过则直接返回
  2. 若i==j只有一块了，直接计算，返回
  3. dp[i][j][len]=max(当前自己和之后合并, 和前面的大块合并并和之后的大块合并)

详细内容可参考此博客(写的很好哦)：Bolcks

代码如下：

#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 210, M = 2e5 + 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m;
int dp[N][N][N];
map<char, int> cost;

struct Box
{
    int color, len;
}box[N];

int dfs(int i, int j, int len)
{
    int &v = dp[i][j][len];
    
    if(v != -1) return v;
    
    if(i == j)
    {
        v = (box[j].len + len) * (box[j].len + len);
        return v;
    }
    
    // 直接点，自己合并
    v = dfs(i, j - 1, 0) + (box[j].len + len) * (box[j].len + len);
    
    // 和前面的一起合并
    for (int k = i; k <= j - 1; k ++ )
        if(box[k].color == box[j].color)
            v = max(v, dfs(i, k, box[j].len + len) + dfs(k + 1, j - 1, 0));
            
    return v;
}

void solve()
{
    memset(dp, -1, sizeof dp);
    memset(box, 0, sizeof box);
    
    cin >> n;
    
    int x, t = -1, idx = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x;
        if(x != t)
        {
            idx ++;
            box[idx].len ++;
            box[idx].color = x;
            t = x;
        }
        else box[idx].len ++;
    }
    
    cout << "Case " << cases << ": " << dfs(1, idx, 0) << endl;
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    cin >> T;
    
    for (cases = 1; cases <= T; cases ++)
        solve();
    
    return 0;
}
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