社区讨论

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 条回复,欢迎继续交流。

正在加载回复...