題目鏈接
題目翻譯：
廚師Monocarp剛剛把n道菜放進了烤箱，他知道第i道菜最佳的烹飪時間是ti 分鐘，
在任何正整數時間點T，Monocarp最多只能從烤箱中拿出一道菜，如果第i道菜在第T分鐘拿出來，那么其不高興值為 |T-ti| ，一旦菜從烤箱拿出來，就不能再放回去，
Monocarp需要將所有菜從烤箱拿出來，求他能得到的最小不開心值，
解題思路：
動態規劃，用陣列f[i][j] 表示在第i分鐘拿出前j道菜得到的最小不開心值，
對于每個i和j，有兩種情況，在第i分鐘，要么取第j道菜，要么不取第j道菜，
如果取，那就是在前i-1分鐘取完前j-1道菜，然后在第i分鐘取第j道菜，那么不開心值就是f[i-1][j-1]+abs(t[j]-i)，其中t[j]表示第j道菜的最佳烹飪時間，
如果不取，那就是在前i-1分鐘就取完了前j道菜，不開心值就是f[i-1][j]，
所以狀態轉移公式就是f[i][j]=min(f[i-1][j],f[i-1][j-1]+abs(t[j]-i))，
還有一個問題是i的范圍是多少，因為ti≤n，所以在得到最小不開心值的前提下，在2*n時間內能取完所有的菜，
代碼：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 410;
int T,n,t[N],f[N][N];
int main() {
// freopen("1.txt","r",stdin);
cin>>T;
while(T--) {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>t[i];
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
f[i][j]=inf;
}
}
sort(t+1,t+n+1);
f[0][0]=0;
for(int i=1;i<=2*n;i++){
f[i][0]=0;
for(int j=n;j>=1;j--){
f[i][j]=min(f[i-1][j],f[i-1][j-1]+abs(t[j]-i));
}
}
cout<<f[2*n][n]<<endl;
}
return 0;
}
代碼優化：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 410;
int T,n,t[N],f[N];
int main() {
// freopen("1.txt","r",stdin);
cin>>T;
while(T--) {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>t[i];
}
for(int i=0;i<N;i++){
f[i]=inf;
}
sort(t+1,t+n+1);
f[0]=0;
for(int i=1;i<=2*n;i++){
for(int j=n;j>=1;j--){
f[j]=min(f[j],f[j-1]+abs(t[j]-i));
}
}
cout<<f[n]<<endl;
}
return 0;
}
總結：
感覺自己應該寫出來的，畢竟這種題目和自己之前刷的題差差不多，
盡管時間充裕，
還是得多刷刷動態規劃
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/196263.html
標籤：其他