社区讨论
MLE27求助!!!
P1233[ICPC 2001 Taejon R] 木棍加工参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lv7qq9gt
- 此快照首次捕获于
- 2024/04/20 14:50 2 年前
- 此快照最后确认于
- 2024/04/20 16:52 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=5001;
int h[N][N],dp[N][N],a[N][N],cnt=0,ans=0,n; // h数组用于记录每套系统,dp用于动态规划存储到目前位置最大的,a数组存储输入序列,cnt记录需要的系统数,ans记录最多能跳过的(口丕)
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i][i];//输入
dp[n][n]=1;//同时初始化dp数组的每个元素为1(每个至少可以被一套系统使用)
}
for(int i=1;i<=n;i++){ // 遍历
for(int j=1;j<i;j++){ // 内循环遍历当前文物之前的所有文物
if(a[i][i]<=a[j][j]){
dp[i][i]=max(dp[i][i],dp[j][j]+1); // 如果当前文物小于等于之前的文物,则更新dp[i](当前文物可以接在之前文物的序列末尾)
}
}
bool flag=1; // 标志位,标记当前文物是否需要新的
int k=-1; // 用于记录可以使用当前的、《耐久》最低的系统的索引
for(int j=1;j<=cnt;j++){ //遍历每个系统
if(h[j][j]>=a[i][i]){ //如果系统能够
flag=0;//设置标志位为不需要新系统
if(k==-1||h[j][j]< h[k][k]){ // 如果是第一个找到的系统或者找到更合适的系统(更低)
k=j; // 更新找到的系统索引
}
}
}
if(flag==1){ // 如果需要新的
h[++cnt][++cnt]=a[i][i]; // 分配新的并记录
}
else{ //如果找到了
h[k][k]=a[i][i]; //更新该系统
}
ans=max(ans,dp[i][i]-1); // 更新最多能.......
}
cout<<ans<<endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...