Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- for(int i=1;i<=n;i++) {
- rsq[i]=rsq[i-1]+arr[i];
- }
- int dp[n+1][k+1];
- for(int i=0;i<=n;i++) {
- for(int j=0;j<=k;j++) {
- dp[i][j]=987654321;
- }
- }
- dp[0][0]=0;
- for(int i=1;i<=n;i++) {
- dp[i][1]=rsq[i];
- }
- for(int i=1;i<=k;i++) {
- dp[1][i]=arr[1];
- }
- for(int i=2;i<=n;i++) {
- for(int j=2;j<=k;j++) {
- for(int x=1;x<i;x++) {
- int s=max(dp[x][j-1], rsq[i]-rsq[x]);
- if(dp[i][j]>s) dp[i][j]=s;
- }
- }
- }
- cout<<dp[n][k];
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement