首页 > 代码库 > Problem D: 勤奋的涟漪2 dp + 求导

Problem D: 勤奋的涟漪2 dp + 求导

2024-08-25 05:00:11   217人阅读

http://www.gdutcode.sinaapp.com/problem.php?cid=1049&pid=3

 

dp[i][state]表示处理了前i个，然后当前状态是state的时候的最小休息天数。

比如用1代表休息，2是训练，3是运动。

如果当前这天允许的状态只是训练。

那么dp[i][3] = inf（表示不可能）

休息是无论何时都可能的了。从dp[i - 1][1--3]个状态转过来， ＋　１即可

 

那个求导是-24

 

技术分享 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

const int maxn = 100 + 20;
int dp[maxn][4];
void work() {
    int n;
    scanf("%d", &n);
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        if (x == 0) {
            dp[i][1] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
            dp[i][2] = dp[i][3] = inf;
        } else if (x == 1) {
            dp[i][2] = dp[i - 1][1];
            dp[i][2] = min(dp[i][2], dp[i - 1][3]);
            dp[i][1] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
            dp[i][3] = inf;
        } else if (x == 2) {
            dp[i][2] = inf;
            dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
        } else if (x == 3) {
            dp[i][1] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]);
            dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]);
        }
    }
    int ans = inf;
    for (int i = 1; i <= 3; ++i) {
        ans = min(ans, dp[n][i]);
    }
    cout << ans * (-24) << endl;
}
int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    while (t--) work();
    return 0;
}
View Code

 

Problem D: 勤奋的涟漪2 dp + 求导


联系
我们