社区讨论
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;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...