Codeforces 1324E Sleeping Schedule DP

题意

给你一个长度为\(n\)的数组\(a\)和3个数字\(h,l和r\)。\(t\)初始为0，每次可以使\(t=(t+a_i) \% h\)或者\(t=(t+a_i-1)\%h\)，如果这时\(t\in\left[l,r\right]\)就将\(ans\)加1。求\(ans\)的最大值。

解题思路

这场比赛的题感觉偏简单了。

这是一道显而易见的DP题。\(dp_{i,j,k}\)表示枚举到\(a_i\)，当前\(t=j\)，是否-1时的\(ans\)的最大值，很容易就能推导出转移公式。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pi;

#define x first

#define y second

#define sz(x) ((int)(x).size())

#define all(x) (x).begin(),(x).end()

#define rall(x) (x).rbegin(),(x).rend()

#define endl '\n'

const double PI=acos(-1.0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l,int r){return l+rng()%(r-l+1);}

namespace IO{

    bool REOF = 1; //为0表示文件结尾

    inline char nc() {

        static char buf[100000], *p1 = buf, *p2 = buf;

        return p1 == p2 && REOF && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? (REOF = 0, EOF) : *p1++;

    }

    template<class T>

    inline bool read(T &x) {

        char c = nc();bool f = 0; x = 0;

        while (c<'0' || c>'9')c == '-' && (f = 1), c = nc();

        while (c >= '0'&&c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = nc();

        if(f)x=-x;

        return REOF;

    }

    template<typename T, typename... T2>

    inline bool read(T &x, T2 &... rest) {

        read(x);

        return read(rest...);

    }

    inline bool need(char &c) { return ((c >= 'a') && (c <= 'z')) || ((c >= '0') && (c <= '9')) || ((c >= 'A') && (c <= 'Z')); }

    // inline bool need(char &c) { return ((c >= 'a') && (c <= 'z')) || ((c >= '0') && (c <= '9')) || ((c >= 'A') && (c <= 'Z')) || c==' '; }

    inline bool read_str(char *a) {

        while ((*a = nc()) && need(*a) && REOF)++a; *a = '\0';

        return REOF;

    }

    inline bool read_dbl(double &x){

        bool f = 0; char ch = nc(); x = 0;

        while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=nc();}

        while(ch>='0'&&ch<='9'){x=x*10.0+(ch^48);ch=nc();}

        if(ch == '.') {

            double tmp = 1; ch = nc();

            while(ch>='0'&&ch<='9'){tmp=tmp/10.0;x=x+tmp*(ch^48);ch=nc();}

        }

        if(f)x=-x;

        return REOF;

    }

    template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }

    template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {

        while(*sdbg!=',')cerr<<*sdbg++;

        cerr<<'='<<h<<','<<' '; _dbg(sdbg+1, a...);

    }

    template<class T> ostream &operator<<(ostream& os, vector<T> V) {

        os << "["; for (auto vv : V) os << vv << ","; return os << "]";

    }

    template<class T> ostream &operator<<(ostream& os, set<T> V) {

        os << "["; for (auto vv : V) os << vv << ","; return os << "]";

    }

    template<class T> ostream &operator<<(ostream& os, map<T,T> V) {

        os << "["; for (auto vv : V) os << vv << ","; return os << "]";

    }

    template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {

        return os << "(" << P.st << "," << P.nd << ")";

    }

    #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

}

using namespace IO;

const int maxn=2e5+5;

const int maxv=2e5+5;

const int mod=998244353; // 998244353 1e9+7

const int INF=1e9+7; // 1e9+7 0x3f3f3f3f 0x3f3f3f3f3f3f3f3f

const double eps=1e-12;

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

//int dx[8]={1,0,-1,1,-1,1,0,-1};

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

//int dy[8]={1,1,1,0,0,-1,-1,-1};

// #define ls (x<<1)

// #define rs (x<<1|1)

// #define mid ((l+r)>>1)

// #define lson ls,l,mid

// #define rson rs,mid+1,r

// int tot,head[maxn];

// struct Edge{

// 	int v,nxt;

//     Edge(){}

//     Edge(int _v,int _nxt):v(_v),nxt(_nxt){}

// }e[maxn<<1];

// void init(){

// 	tot=1;

// 	memset(head,0,sizeof(head));

// }

// void addedge(int u,int v){

// 	e[tot]=Edge(v,head[u]); head[u]=tot++;

// 	e[tot]=Edge(u,head[v]); head[v]=tot++;

// }

// void addarc(int u,int v){

//     e[tot]=Edge(v,head[u]); head[u]=tot++;

// }

/**

 * **********     Backlight     **********

 * 仔细读题

 * 注意边界条件

 * 记得注释输入流重定向

 * 没有思路就试试逆向思维

 * 加油，奥利给

 */

int n,h,l,r,a[maxn];

int dp[2005][2005][2];

void solve(){

    read(n,h,l,r);

    for(int i=1;i<=n;i++)read(a[i]);

    memset(dp,-1,sizeof(dp));

    dp[0][0][0]=dp[0][0][1]=0;

    int sleep,delta;

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

        for(int j=0;j<h;j++){

            if(dp[i-1][j][0]!=-1){

                sleep=(j+a[i])%h;

                delta=(sleep>=l && sleep<=r)?1:0;

                dp[i][sleep][0]=max(dp[i][sleep][0],dp[i-1][j][0]+delta);

                sleep=(j+a[i]-1)%h;

                delta=(sleep>=l && sleep<=r)?1:0;

                dp[i][sleep][1]=max(dp[i][sleep][1],dp[i-1][j][0]+delta);

            }

            if(dp[i-1][j][1]!=-1){

                sleep=(j+a[i])%h;

                delta=(sleep>=l && sleep<=r)?1:0;

                dp[i][sleep][0]=max(dp[i][sleep][0],dp[i-1][j][1]+delta);

                sleep=(j+a[i]-1)%h;

                delta=(sleep>=l && sleep<=r)?1:0;

                dp[i][sleep][1]=max(dp[i][sleep][1],dp[i-1][j][1]+delta);

            }

        }

    }

    int ans=0;

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

        ans=max(ans,dp[n][i][0]);

        ans=max(ans,dp[n][i][1]);

    }

    printf("%d\n",ans);

}

int main()

{

    // freopen("in.txt","r",stdin);

    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    // int _T; read(_T); for(int _=1;_<=_T;_++)solve();

    // while(read(n))solve();

    solve();

    return 0;

}

巴特西

Codeforces 1324E Sleeping Schedule DP

题意

解题思路

AC代码

最新文章

热门文章