NC214713. Forest(EasyVersion)
描述
There is a magic forest with n trees. Trees in the forest stand in a line, marked 1 to n from left to right. The initial height of the i-th tree is ai meters. Binbin likes these trees. She wants to use her magic to make these trees higher so that she can see many trees when stands at the most left of the forest. Assuming that 1 magic point makes a tree grow by 1 meter and the height of a tree can’t be decreased, she would like to know what's the minimum number of magic points she has to spend to make at least k trees visible. You need to find the answer for every k from 1 to n. The i-th tree is visible when ai>aj for any j<i.
输入描述
The first line contains an integer n (1<=n<=100), represents the number of trees in the forest. The second line contains n integers a1,a2,a3,...,an (1<=ai<=1,000,000,000),represents the initial heights of each tree from left to right.
输出描述
Print n integers in a single line separated by a blank. The i-th integer represents the minimum magic points she needs to spend to make at least i trees visible.
示例1
输入:
5 5 3 4 5 7
输出:
0 0 1 5 11
说明:
Initially, the 1-st and the 5-th trees are visible. (1 5)
Then, Binbin spends 1 magic point on the 4-th tree so there are three trees visible now. (1 4 5)
5 3 4 5 7 → 5 3 4 6 7
To make four trees visible, Binbin can spend 2 magic points on the 3-rd tree, 2 magic points on the 4-th tree and 1 magic point on the 5-th tree, 5 totally. (1 3 4 5)
5 3 4 5 7 → 5 3 6 7 8
Binbin spends 11 magic points at least to make five trees visible. (1 2 3 4 5)
C++(clang++11) 解法, 执行用时: 14ms, 内存消耗: 4344K, 提交时间: 2021-01-22 15:32:00
#include<bits/stdc++.h>
using namespace std;
const int N=105;
typedef long long ll;
#define x first
#define y second
map<int,ll>f[N][N];
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0][0][0]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(auto p:f[i][j])
{
int k=p.x;
int mh=max(k,a[i+1]);
if(!f[i+1][j].count(mh))
f[i+1][j][mh]=f[i][j][k];
else
f[i+1][j][mh]=min(f[i+1][j][mh],f[i][j][k]);
if(a[i+1]>k)
{
if(!f[i+1][j+1].count(a[i+1]))
f[i+1][j+1][a[i+1]]=f[i][j][k];
else
f[i+1][j+1][a[i+1]]=min(f[i+1][j+1][a[i+1]],f[i][j][k]);
}
else
{
if(!f[i+1][j+1].count(k+1))
f[i+1][j+1][k+1]=f[i][j][k]+k+1-a[i+1];
else
f[i+1][j+1][k+1]=min(f[i+1][j+1][k+1],f[i][j][k]+k+1-a[i+1]);
}
}
}
}
for(int i=1;i<=n;i++)
{
ll ans=1e12;
for(auto p:f[n][i])
ans=min(ans,p.y);
cout<<ans<<" ";
}
cout<<endl;
return 0;
}