社区讨论

58pts TLE求调

P1135奇怪的电梯参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mjjzt1ot
此快照首次捕获于
2025/12/24 20:31
3 个月前
此快照最后确认于
2025/12/26 23:55
2 个月前
查看原帖
可以看出,我用的是dp的做法,但我在#1~#6,#15的测试点都TLE了。
CPP
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define For(i,a,b,c) for(register int i = (a),i##end = (int)(b); i <= i##end;i += (c))
#ifdef __unix__
    #define gc getchar_unlocked
    #define pc putchar_unlocked
#else
    #define gc _getchar_nolock
    #define pc _putchar_nolock
#endif
ll read(){
    ll x = 0;
    bool f = 1;
    char ch = gc();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = 0;
        ch = gc();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = gc();
    }
    return x * (f ? 1ll : -1ll);
}
void write(ll x){
    if(x == 0){
        pc('0');
        return;
    }
    if(x < 0){
        pc('-');
        if(x == LLONG_MIN){
            write((-x) / 10);
            pc('8');
            return;
        }
        x = -x;
    }
    if(x < 10){
        pc(x + '0');
        return;
    }
    ll rev = 0,cnt = 0;
    do{
        rev = rev * 10 + (x % 10),x /= 10,cnt++;
    }while(x);
    do{
        pc('0' + (rev % 10)),rev /= 10;
    }while(--cnt);
    return;
}
ll k[205],dp[205],tmp[205];
namespace operation{
    template<typename T>
    bool compare(const T* a,const T* b,size_t size){
        if(a == nullptr || b == nullptr || size <= 0) return false;
        if(a == b) return true;
        return equal(a,a + size,b);
    }
    template<typename T>
    void copy(const T* a,T* b,size_t size){
        if(a == nullptr || b == nullptr || size <= 0 || a == b) return;
        std::copy(a,a + size,b);
        return;
    }
};
int main() {
    
    memset(dp,0x7f,sizeof dp);
    ll n = read(),a = read(),b = read();
    For(i,1,n,1) k[i] = read();
    dp[a] = 0;
    while(!operation::compare(dp,tmp,n+1)){
        operation::copy(dp,tmp,n+1);
        For(i,1,n,1){
            dp[i+k[i]] = min(dp[i+k[i]],dp[i]+1);
            dp[i-k[i]] = min(dp[i-k[i]],dp[i]+1);
        }
    }
    if(dp[b] != 0x7f7f7f7f7f7f7f7f) write(dp[b]);
    else write(-1);
    
    return 0;
}
我觉得应该是dp推导的问题,时间复杂度肉眼可见地高。

回复

5 条回复,欢迎继续交流。

正在加载回复...