發表新討論
#27252: 想問問看有沒有人知道我怎麼會RE


johnnyli122022@gmail.com (李小佑)

學校 : 臺北市立成功高級中學
編號 : 144028
來源 : [180.177.13.123]
最後登入時間 ：
2024-01-15 16:17:32
f173. m6a1-作物種植(Plant) -- TOI練習賽2020年6月潛力組 | From: [61.228.61.58] | 發表日期 : 2021-09-20 23:19 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
pair<int,int> p[10010];
vector <int> v[10010];
bool cmp(pair<int,int>x, pair<int,int>y){
	return x.f<=y.f;
}
int dp[10010][10010];
int main(){
	int l, t;
	scanf("%d%d", &l, &t);
	for(int i=1; i<=t; i++){
		scanf("%d%d", &p[i].f, &p[i].s);
		v[p[i].s].push_back(p[i].f);
	}
	sort(p+1, p+t+1, cmp);
	for(int i=1; i<=t; i++){
		for(int j=1; j<=l; j++){
			if(v[j].empty()) dp[i][j]=dp[i][j-1];
			else{
				dp[i][j]=dp[i][j-1];
				for(int u:v[j]){
					dp[i][j]=max(dp[i-1][u]+j-u, dp[i][j]);
				}
			} 
		}
	}
	printf("%d", dp[t][l]);
}
我在DEV C++和C++ shell 都會有正確結果
 
#29380: Re:想問問看有沒有人知道我怎麼會RE


lai.abc8660@gmail.com (alan lai)

學校 : 臺北市立成功高級中學
編號 : 81120
來源 : [180.176.149.15]
最後登入時間 ：
2023-12-18 22:49:26
f173. m6a1-作物種植(Plant) -- TOI練習賽2020年6月潛力組 | From: [180.176.149.15] | 發表日期 : 2022-02-21 20:20 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
pair<int,int> p[10010];
vector <int> v[10010];
bool cmp(pair<int,int>x, pair<int,int>y){
	return x.f<=y.f;
}
int dp[10010][10010];
int main(){
	int l, t;
	scanf("%d%d", &l, &t);
	for(int i=1; i<=t; i++){
		scanf("%d%d", &p[i].f, &p[i].s);
		v[p[i].s].push_back(p[i].f);
	}
	sort(p+1, p+t+1, cmp);
	for(int i=1; i<=t; i++){
		for(int j=1; j<=l; j++){
			if(v[j].empty()) dp[i][j]=dp[i][j-1];
			else{
				dp[i][j]=dp[i][j-1];
				for(int u:v[j]){
					dp[i][j]=max(dp[i-1][u]+j-u, dp[i][j]);
				}
			} 
		}
	}
	printf("%d", dp[t][l]);
}
我在DEV C++和C++ shell 都會有正確結果

你確定這樣不會tle嗎，有更好的轉移式(同題：帶權的時間排程dp)

 

至於re我也不知道，但醬應該過不了

 
#29382: Re:想問問看有沒有人知道我怎麼會RE


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13
f173. m6a1-作物種植(Plant) -- TOI練習賽2020年6月潛力組 | From: [111.248.153.164] | 發表日期 : 2022-02-21 22:27 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
pair<int,int> p[10010];
vector <int> v[10010];
bool cmp(pair<int,int>x, pair<int,int>y){
	return x.f<=y.f;
}
int dp[10010][10010];
int main(){
	int l, t;
	scanf("%d%d", &l, &t);
	for(int i=1; i<=t; i++){
		scanf("%d%d", &p[i].f, &p[i].s);
		v[p[i].s].push_back(p[i].f);
	}
	sort(p+1, p+t+1, cmp);
	for(int i=1; i<=t; i++){
		for(int j=1; j<=l; j++){
			if(v[j].empty()) dp[i][j]=dp[i][j-1];
			else{
				dp[i][j]=dp[i][j-1];
				for(int u:v[j]){
					dp[i][j]=max(dp[i-1][u]+j-u, dp[i][j]);
				}
			} 
		}
	}
	printf("%d", dp[t][l]);
}
我在DEV C++和C++ shell 都會有正確結果

你確定這樣不會tle嗎，有更好的轉移式(同題：帶權的時間排程dp)

 

至於re我也不知道，但醬應該過不了

電欸 帶權的DP 跟鬼一樣

 
ZeroJudge Forum