$dp[i]$表示前i个数字组成的最小答案，得到状态转移方程
$$ dp[i]={min(\
dp[i-1]+a[i],\
dp[i-c]+sum_{j=i-c+1}^{i}a[i]-min_{j=i-c+1}^{i}a[i]
\) }
$$
维护动态集合（有不停的添加删除元素）的最小值用muiltset
总结
解题时要想到枚举思路，dp，二分，贪心等常用思路都要考虑到。当确定$dp[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
|
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
#define L index*2
#define R index*2+1
using namespace std;
typedef long long ll;
const ll MAXN=1e6+100;
const ll MOD=1e9+7;
ll arr[MAXN];
ll dp[MAXN];
ll sum[MAXN];
multiset<ll> se;
int (int argc, char const *argv[]) {
ll n,c;
while (cin>>n>>c) {
se.clear();
for(int i=1;i<=n;++i)
scanf("%lld",&arr[i]);
sum[0]=0;
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+arr[i];
dp[0]=0;
for(int i=1;i<c;++i)
{
dp[i]=dp[i-1]+arr[i];
se.insert(arr[i]);
}
for(int i=c;i<=n;++i)
{
se.insert(arr[i]);
dp[i]=min(dp[i-1]+arr[i],dp[i-c]+sum[i]-sum[i-c]-*(se.begin()));
se.erase(se.find(arr[i-c+1]));
}
cout<<dp[n]<<endl;
}
return 0;
}
|
近期评论