Minimum Price after Suffix Sign Flips
Autumn Tournament (2021)
Submission name: price.cpp
Problem summary
You will buy all N shops, whose prices may be positive, zero or negative. One operation chooses a position p and negates every price from p through N. Perform at most K operations to minimize the final sum.
Input
N K, then N integer prices.
Output
The smallest possible total price.
Constraints
1 ≤ N ≤500000; 1 ≤ K ≤100; |price|≤1000000000.
Worked example
Original statement sample.
Input
6 2 -1 10 6 5 -2 -3
Output
-27
Solution analysis
- Suffix flips commute: only their chosen starting positions matter. Applying two flips at the same position cancels, so an optimal at-most-K solution never needs that repetition. Scan positions left to right and decide whether a flip starts before the current price.
- Use dp[j][parity] for the minimum sum of the processed prefix with exactly j flip starts and the indicated active sign parity. Before adding a price, either retain parity or start a new flip, consuming one operation and switching parity. Add a[i] in parity 0 and−a[i] in parity 1.
- Update j in decreasing order so dp[j−1] still refers to the previous position. At the end take the minimum over all j≤K and both parities. In the sample, flip the suffix at 2 and then at 5: prices become−1,−10,−6,−5,−2,−3, whose sum is−27.
Why it works
Every subset of flip starting positions determines one parity sequence and is represented by the DP decisions. Conversely, each DP transition either starts a legal suffix operation or does nothing, so every represented sequence is achievable. Since a processed price is affected only by starts at or before it, adding its parity-adjusted value gives the exact objective. Taking minima preserves the best cost for every state.
Watch out. The limit is at most K, not exactly K. Parity must persist to later positions. Updating j upward would reuse the current position incorrectly; either use separate old/new arrays or the descending update shown.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int k;
cin>>n>>k;
k=min(k,n);
const long long infinity=numeric_limits<long long>::max()/4;
vector<array<long long,2>>dp(k+1,{infinity,infinity});
dp[0][0]=0;
for(int i=1;i<=n;i++){
long long price;
cin>>price;
for(int used=min(i,k);used>=0;used--){
long long keepPositive=dp[used][0];
long long keepNegative=dp[used][1];
if(used>0){
// Lower-index states still belong to the preceding prefix.
keepPositive=min(keepPositive,dp[used-1][1]);
keepNegative=min(keepNegative,dp[used-1][0]);
}
dp[used][0]=keepPositive==infinity?infinity:keepPositive+price;
dp[used][1]=keepNegative==infinity?infinity:keepNegative-price;
}
}
long long answer=infinity;
for(const auto&state:dp){
answer=min(answer,min(state[0],state[1]));
}
cout<<answer<<'\n';
}