Timus: DP

1119.cpp

#include <iostream>
#include <cmath>
using namespace std;

constexpr int MAXN = 1e3 + 1;
double grid[MAXN][MAXN];

int main(void)
{
    int n, m, k;
    cin >> n >> m >> k;
    double r = sqrt(2e4);

    while (k--)
    {
        int i, j;
        cin >> i >> j;
        grid[i][j] = -1;
    }

    // base cases:
    for (int i = 1; i <= n; i++)
        grid[i][0] = i * 100;
    for (int j = 1; j <= m; j++)
        grid[0][j] = j * 100;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (grid[i][j] == -1)
                grid[i][j] = r + grid[i - 1][j - 1];
            else
                grid[i][j] = 100 + min(grid[i - 1][j], grid[i][j - 1]);

    cout << round(grid[n][m]) << "\n";
}

1225.cpp

// Observation: The last stripe of any window must be red or white.
#include <iostream>
using namespace std;

using ll = long long;
constexpr int MAXN = 46;
enum Color { R, W };

ll window[MAXN][2];
// window[i][R]: how many decoration of i-stripe ends with red.
// window[i][W]: how many decoration of i-stripe ends with white.
ll solve(int n)
{
    // base cases
    window[1][W] = window[1][R] = 1;
    window[2][W] = window[2][R] = 1;

    // Observation: if the last stripe is red, then the penultimate stripe
    // xor the third last stripe must be white, and vice versa.
    for (int f = 3; f <= n; f++)
    {
        window[f][R] = window[f - 1][W] + window[f - 2][W];
        window[f][W] = window[f - 1][R] + window[f - 2][R];
    }
    return window[n][R] + window[n][W];
}

ll flag[MAXN];
// flag[i]: how many decoration of i-stripe ends with red/white.
ll solve2(int n)
{
    flag[1] = 2;
    flag[2] = 2;

    for (int f = 3; f <= n; f++)
        flag[f] = flag[f - 1] + flag[f - 2];

    return flag[n];
}

int main(void)
{
    int n;
    cin >> n;
    cout << solve(n) << "\n";
    cout << solve2(n) << "\n";
}

1353.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int table[10][82];
// table[p][x]: in how many ways SOD can be x, up to pth position (rtl)?

int main(void)
{
    // base cases:
    for (int s = 0; s <= 9; s++)
        table[1][s] = 1;

    for (int p = 2; p <= 9; p++)
        for (int s = 0; s <= 81; s++)
            for (int d = 0; d <= 9 && s - d >= 0; d++) // current digit
                table[p][s] += table[p - 1][s - d];

    int s;
    cin >> s;
    cout << table[9][s] + (s == 1) << "\n";
}

2018.cpp

#include <iostream>
using namespace std;

constexpr int MAXN = 5e4 + 1;
constexpr int MOD = 1e9 + 7;
int table[MAXN][2];
// table[i][0]: with an i-song album, in how many ways can the last song be 1?
// table[i][1]: with an i-song album, in how many ways can the last song be 2?

inline int sum(int a, int b)
{
    return (a + b) % MOD;
}

int main(void)
{
    int n, a, b;
    cin >> n >> a >> b;

    table[0][0] = table[0][1] = 1; // sentinels
    // Think about it in this way: we can be at position 0, and have the option
    // to choose 0 or 1 for the next positions.
    // If there were no such way to be at position 0 and make those decisions, 
    // we would say T[0][0] = T[0][1] = 0.

    for (int i = 0; i < n; i++) // done up to this position.
    {
        // We can be at position i, where the ith element is 2, in T[i][1] many ways.
        // Each of the next A position(s) can be 1 in a valid permutation.
        
        // Say, there are X ways to be at position P, where P is 2, and it is valid 
        // to have upto A many 1's contiguously. 
        // If we choose 1 for a particular position Q, we have X many valid permutation 
        // with these setup: the Pth position is 2, and the Qth position is 1. 
        // This statement holds for each of the next A positions from P.
        
        // The same kind of rational applies when the Pth position holds 1 instead of 2.
        
        for (int j = 1; j <= a && i + j <= n; j++)
            table[i + j][0] = sum(table[i + j][0], table[i][1]);

        for (int j = 1; j <= b && i + j <= n; j++)
            table[i + j][1] = sum(table[i + j][1], table[i][0]);
    }

    cout << sum(table[n][0], table[n][1]) << "\n";
}