Problèmes de programmation dynamique

DP linéaire, traitements de données séparés Problème : P1095

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int m, s, t, flash[N], waiting_time[N]; // Calcul séparé pour courir ou attendre
int main()
{
    cin >> m >> s >> t;
    for (int i = 1; i <= t; i++)
    {
        if (m >= 10)
        {
            m -= 10;
            flash[i] = flash[i - 1] + 60;
            waiting_time[i] = max(waiting_time[i - 1] + 17, flash[i]);
        } // Si possible, utiliser le flash
        else
        {
            m += 4;
            flash[i] = flash[i - 1];
            waiting_time[i] = waiting_time[i - 1] + 17;
        } // Si impossible, enregistrer le temps
    }
    for (int i = 1; i <= t; i++)
    {
        if (waiting_time[i] >= s)
        {
            cout << "Oui" << endl
                 << i << endl;
            return 0;
        }
    }
    cout << "Non" << endl
         << waiting_time[t] << endl;
    return 0;
}

Problème du sac à dos Problème : P1077

#include <bits/stdc++.h>
using namespace std;

int main()
{
    const int N = 300;
    const int mod_value = 1000007;
    int n_items, max_weight, item_weights[N], dp_table[N][N];
    cin >> n_items >> max_weight;
    for (int i = 1; i <= n_items; i++)
        cin >> item_weights[i];
    dp_table[0][0] = 1;
    for (int i = 1; i <= n_items; i++)
    {
        for (int j = 0; j <= max_weight; j++)
        {
            for (int k = 0; k <= item_weights[i] && k <= j; k++)
            {
                dp_table[i][j] = (dp_table[i][j] + dp_table[i - 1][j - k]) % mod_value;
            }
        }
    }
    cout << dp_table[n_items][max_weight] % mod_value << endl;
    return 0;
}

Décomposition binaire Problème : P1833

#include <cstdio>
#include <algorithm>
using namespace std;
int x_start, y_start, x_end, y_end, num_items, dp[1010];
int item_values[10005], item_weights[10005], item_counts[10005];
int total_count, decomposed_values[1000005], decomposed_weights[1000005];

void binary_decomposition()
{
    for (int i = 1; i <= num_items; i++)
    {
        int current_power = 1;
        while (item_counts[i] > 0)
        {
            decomposed_values[++total_count] = current_power * item_values[i];
            decomposed_weights[total_count] = current_power * item_weights[i];
            item_counts[i] -= current_power;
            current_power *= 2;
            if (item_counts[i] < current_power)
            {
                decomposed_values[++total_count] = item_values[i] * item_counts[i];
                decomposed_weights[total_count] = item_weights[i] * item_counts[i];
                break;
            }
        }
    }
}

int main()
{
    scanf("%d:%d%d:%d%d", &x_start, &y_start, &x_end, &y_end, &num_items);
    int total_time = (x_end * 60 + y_end) - (x_start * 60 + y_start);
    for (int i = 1; i <= num_items; i++)
    {
        scanf("%d%d%d", &item_values[i], &item_weights[i], &item_counts[i]);
        if (!item_counts[i])
            item_counts[i] = 999999;
    }
    binary_decomposition();
    for (int i = 1; i <= total_count; i++)
    {
        for (int j = total_time; j >= decomposed_values[i]; j--)
            dp[j] = max(dp[j], dp[j - decomposed_values[i]] + decomposed_weights[i]);
    }
    printf("%d", dp[total_time]);
    return 0;
}

Problème de DP linéaire inhabituel Problème : P3842

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 20010
#define int long long
using namespace std;
int n;
int dp_array[MAXN][2], distances[2][2], left_positions[MAXN], right_positions[MAXN];
int sum_array[MAXN];
int inf_value = 0x3f3f3f3f;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&left_positions[i],&right_positions[i]);
    left_positions[0]=right_positions[0]=1;
    left_positions[n+1]=right_positions[n+1]=n;
    for(int i=1;i<=n+1;i++)
    {
        if(left_positions[i-1]<left_positions[i]) 
            distances[0][0]=right_positions[i]-left_positions[i-1]+right_positions[i]-left_positions[i],
            distances[0][1]=right_positions[i]-left_positions[i-1];
        else if(left_positions[i-1]>right_positions[i])
            distances[0][0]=left_positions[i-1]-left_positions[i],
            distances[0][1]=right_positions[i]-left_positions[i]+left_positions[i-1]-left_positions[i];
        else 
            distances[0][0]=2*right_positions[i]-left_positions[i-1]-left_positions[i],
            distances[0][1]=left_positions[i-1]-left_positions[i]+right_positions[i]-left_positions[i];
        if(right_positions[i-1]<left_positions[i])
            distances[1][0]=right_positions[i]-right_positions[i-1]+right_positions[i]-left_positions[i],
            distances[1][1]=right_positions[i]-right_positions[i-1];
        else if(right_positions[i-1]>right_positions[i])
            distances[1][0]=right_positions[i-1]-left_positions[i],
            distances[1][1]=right_positions[i-1]-left_positions[i]+right_positions[i]-left_positions[i];
        else
            distances[1][0]=right_positions[i]-right_positions[i-1]+right_positions[i]-left_positions[i],
            distances[1][1]=right_positions[i-1]-left_positions[i]+right_positions[i]-left_positions[i];
        dp_array[i][0]=min(dp_array[i-1][0]+1+distances[0][0], dp_array[i-1][1]+1+distances[1][0]);
        dp_array[i][1]=min(dp_array[i-1][0]+1+distances[0][1], dp_array[i-1][1]+1+distances[1][1]);
    }
    printf("%lld\n",min(dp_array[n+1][0], dp_array[n+1][1])-2); 
    return 0;
}

Fusion de pierres en ligne circulaire

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n, stones[N], dp_table[N][N], min_dp[N][N];
int prefix_sum[N];
const int inf = 0x3f3f3f3f;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> stones[i];
    int max_value = 0, min_value = 0x3f3f3f3f;
    for (int start = 0; start < n; start++)
    {
        memset(prefix_sum, 0, sizeof(prefix_sum));
        for (int pos = start; pos < start + n; pos++)
        {
            int idx = pos - start + 1;
            prefix_sum[idx] = prefix_sum[idx - 1] + stones[pos % n];
        }
        memset(dp_table, 0, sizeof(dp_table));
        memset(min_dp, inf, sizeof(min_dp));
        for (int i = 1; i <= n; i++)
            min_dp[i][i] = 0;

        for (int i = n - 1; i >= 1; i--)
            for (int j = i + 1; j <= n; j++)
                for (int k = i; k <= j - 1; k++)
                {
                    dp_table[i][j] = max(dp_table[i][j], dp_table[i][k] + dp_table[k + 1][j] + prefix_sum[j] - prefix_sum[i - 1]);
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j] + prefix_sum[j] - prefix_sum[i - 1]);
                }
        if (max_value < dp_table[1][n])
            max_value = dp_table[1][n];
        if (min_value > min_dp[1][n])
            min_value = min_dp[1][n];
    }
    cout << min_value << endl
         << max_value << endl;
    return 0;
}