• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

273. 分级

开发技术 开发技术 2周前 (04-06) 8次浏览

题目链接:https://www.acwing.com/problem/content/275/

思路:首先要知道一个性质 : 一定存在一组最优解b[i] 使得每个b[i]都在a[i] 中出现过 证明略

然后考虑dp[i][j] 代表前i个a[i] 一定匹配好 且b中最后一个数是b[j]  的最小值 

可以知道 dp[i][j] =abs(a[i]-b[j]) 即当前这个贡献和 前面要最小的贡献  

前面最小的贡献  是 dp[i-1][k]  k=1~j 这样转移的话就需要三重循环  但是可以发现

可以用一个mi  边跑j循环的时候 边记录下dp[i-1][k] 的最小值 这样就是两重循环

单调递增只需要 升序排序即可  递减就 降序排序 dp即可

273. 分级273. 分级

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e3+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair<int,int>
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 
12 int dp[maxn][maxn];
13 int a[maxn],b[maxn];
14 int n;
15 
16 int solve()
17 {
18     int ans=1e9;
19     for(int i=1;i<=n;i++)
20     {
21         int mi=1e9;
22         for(int j=1;j<=n;j++)
23         {
24             mi=min(mi,dp[i-1][j]);
25             dp[i][j]=mi+abs(a[i]-b[j]);
26         }
27     }
28     for(int i=1;i<=n;i++) ans=min(ans,dp[n][i]);
29     return ans;
30 }
31 
32 
33 int main()
34 {
35     ios::sync_with_stdio(false);
36     cin.tie(0);
37     cin>>n;
38     for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
39     sort(b+1,b+1+n);
40     int ans=1e9;
41     ans=solve();
42 
43 
44 
45     sort(b+1,b+1+n,greater<int>());
46     ans=min(ans,solve());
47 
48     cout<<ans<<'n';
49 
50 
51 
52 
53 }

View Code

 


程序员灯塔
转载请注明原文链接:273. 分级
喜欢 (0)