C. Chef Monocarp
有n<200个食物在微波炉里每个食物有个完成时刻 $t_i$
每分钟只能从微波炉里拿一盘菜出来
对于这盘菜产生的不满意度=|$t_i$-T| 其中T为当前拿出它的时间
问最小的不满意值
设计一个dp(T,i) 表示前t分钟取出前i盘菜 的最优解(先按照每盘菜的完成时刻排序)
一般dp设计思路都是一维表示位置(时间)一维表示状态
于是显然对于前T分钟取出前i盘菜的dp(T,i)
有两种方式转移到它 :
- 到这一分钟我不拿菜 ,即 dp(T-1,i) -> dp(T,i)
- 到这一分钟我拿出一盘菜 ,即dp(T-1,i-1) ->dp(T,i)
进一步说就是 dp(T,i)=min(dp(T-1,i),dp(T-1,i-1)+|T-$t_i$| )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define Turnoff std::ios::sync_with_stdio(false) #define P pair<ll,ll> const int Max=2e5+5; const int Mod=1e9+7; const int inf=0x3f3f3f3f;
int t[204]; int dp[405][205]; int main(){ Turnoff; int q;cin>>q; while(q--){ int n;cin>>n; for(int i=1;i<=n;i++)cin>>t[i]; sort(t+1,t+n+1); memset(dp,0x3f,sizeof dp); for(int i=0;i<405;i++)dp[i][0]=0; for(int i=1;i<405;i++){ for(int j=1;j<=n;j++){ dp[i][j]=min(dp[i][j],dp[i-1][j]); dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs(i-t[j])); } } cout<<dp[404][n]<<endl; } }
|
dp(T,i)=min(dp(T-1,i),dp(T-1,i-1)+|T-$t_i$| ) 发现dp(T-1,i)/dp(T-1,i-1) 总之dp(T-1,x)只会被使用一次
即T-1 -> T 时间维度的转移 完全可以从后往前遍历 来将这一维度省略掉
用类似背包dp的方式省略掉时间维度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define Turnoff std::ios::sync_with_stdio(false) #define P pair<ll,ll> const int Max=2e5+5; const int Mod=1e9+7; const int inf=0x3f3f3f3f;
int t[204]; int dp[405]; int main(){ Turnoff; int q;cin>>q; while(q--){ int n;cin>>n; for(int i=1;i<=n;i++)cin>>t[i]; sort(t+1,t+n+1); memset(dp,0x3f,sizeof dp); dp[0]=0; for(int i=1;i<=405;i++){ for(int j=n;j>=1;j--){ dp[j]=min(dp[j],dp[j-1]+abs(i-t[j])); } } cout<<dp[n]<<endl; } }
|