神秘 max 函数
  • 板块学术版
  • 楼主TH911
  • 当前回复23
  • 已保存回复24
  • 发布时间2025/8/4 20:43
  • 上次更新2025/8/5 13:17:57
查看原帖
神秘 max 函数
967959
TH911楼主2025/8/4 20:43

背景:P1070

先放一个代码:

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1000,M=1000,P=M,inf=0x3f3f3f3f;
int n,m,p,a[N+1][M+1],cost[N+1];
int dp[2][N+1][P+1];
int node(int x){
	x--;
	x%=n;
	if(x<0){
		x+=n;
	}
	x++;
	return x;
}
int max(int a,int b){
	if(a>b){
		return a;
	}
	return b;
}
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		} 
	}
	for(int i=1;i<=n;i++){
		cin>>cost[i];
	}
	bool mode;
	for(int i=1;i<=m;i++){
		mode=!mode;
		int Max;
		if(i==1){
			Max=0;
		}else{
			Max=-inf;
		}
		for(int j=1;j<=n;j++){
			for(int k=0;k<i-1&&k<p;k++){
				Max=max(Max,dp[!mode][j][k]);
			}
		}
		for(int j=1;j<=n;j++){
			dp[mode][j][0]=Max-cost[j]+a[j][i];
			for(int k=1;k<i&&k<p;k++){
				dp[mode][j][k]=dp[!mode][node(j-1)][k-1]+a[j][i];
			}
		}
	}
	int ans=dp[mode][1][0];
	for(int i=1;i<=n;i++){
		for(int j=0;j<m&&j<p;j++){
			ans=max(ans,dp[mode][i][j]);
		}
	}
	cout<<ans<<'\n';
	
	cout.flush();
	 
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

其中,自定义了 max 函数:

int max(int a,int b){
	if(a>b){
		return a;
	}
	return b;
}

显然,这是一个取最大值的函数。但是去除这个定义,换为库函数 max 就会出错。

显然,图中的 max 结果是错误的。

甚至于,更为神奇的是,将 max(a,b) 改为 max({a,b}) 的形式,答案又有变化。但是整个 DP 的最终结果是错误的。

2025/8/4 20:43
加载中...