#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 都會有正確結果
#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我也不知道,但醬應該過不了
#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 跟鬼一樣