f173 - m6a1-作物種植(Plant)
題目描述
題目要求在一個長度為 M 的路段上，從 T 種作物中選擇種植，使得種植作物的總長度最大。每種作物有其起始位置 S 和結束位置 E，且一旦選擇種植某種作物，就必須將該作物種滿整個路段 [S, E]。
解題思路
本題可以使用動態規劃來解決。首先，將所有作物按照起始位置進行排序。然後，使用一個 DP 陣列 DP[i] 來記錄在路段長度為 i 的情況下，可以種植作物的最大長度。對於每種作物，如果它的起始位置為 s，結束位置為 e，則可以考慮將其種植在路段 [s, e] 上。如果種植該作物，則路段 [s, e] 上可以種植的長度為 e - s。因此，可以更新 DP[e] 的值為 max(DP[e], DP[s] + (e - s))。最後，DP[M] 即為可以種植作物的最大長度。
複雜度分析
- 時間複雜度: O(T * M)，其中 T 是作物的數量，M 是路段的總長度。排序需要 O(T log T)，DP 遍歷需要 O(T * M)。因此，總時間複雜度為 O(T log T + T * M)。在最壞情況下，T 和 M 都是 10^4，因此時間複雜度為 O(10^8)。
- 空間複雜度: O(M)，DP 陣列需要 O(M) 的空間。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
struct plant{
int s,e;
};
plant P[10005];
int DP[10005];
inline bool cmp(plant a,plant b){
return a.s<b.s;
}
int main(){
int M=read(),T=read();
for(int i=0;i<T;++i){
P[i].s=read();
P[i].e=read();
}
std::sort(P,P+T,cmp);
for(int i=0;i<T;++i){
int len=DP[P[i].s]+(P[i].e-P[i].s);
for(int j=P[i].e;j<=M;++j){
if(len<=DP[j]) break;
DP[j]=len;
}
}
printf("%d\n",DP[M]);
}