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

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 =  + ;

int dp[maxn][];

void work() {

    int n;

    scanf("%d", &n);

    memset(dp, , sizeof dp);

    for (int i = ; i <= n; ++i) {

        int x;

        scanf("%d", &x);

        if (x == ) {

            dp[i][] = min(dp[i - ][], min(dp[i - ][], dp[i - ][])) + ;

            dp[i][] = dp[i][] = inf;

        } else if (x == ) {

            dp[i][] = dp[i - ][];

            dp[i][] = min(dp[i][], dp[i - ][]);

            dp[i][] = min(dp[i - ][], min(dp[i - ][], dp[i - ][])) + ;

            dp[i][] = inf;

        } else if (x == ) {

            dp[i][] = inf;

            dp[i][] = min(dp[i - ][], dp[i - ][]);

            dp[i][] = min(dp[i - ][], min(dp[i - ][], dp[i - ][])) + ;

        } else if (x == ) {

            dp[i][] = min(dp[i - ][], min(dp[i - ][], dp[i - ][])) + ;

            dp[i][] = min(dp[i - ][], dp[i - ][]);

            dp[i][] = min(dp[i - ][], dp[i - ][]);

        }

    }

    int ans = inf;

    for (int i = ; i <= ; ++i) {

        ans = min(ans, dp[n][i]);

    }

    cout << ans * (-) << 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 ;

}

巴特西

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

最新文章

热门文章