Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
DP Optimization another kind
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define mp make_pair #define pb push_back #define pii pair<int, int> int n, m, a[4001][4001], dp[801][4001], opt[801][4001], cost[4001][4001]; inline int query(int from, int to){ int r1 = from, c1 = from, r2 = to, c2 = to; return (a[r2][c2] - a[r1-1][c2] - a[r2][c1-1] + a[r1-1][c1-1])/2; } void build(){ for(int j = 1; j <= n; j++){ for(int k = 1; k <= m; k++) a[j][k] += a[j][k-1]; } for(int k = 1; k <= m; k++){ for(int j = 1; j <= n; j++) a[j][k] += a[j-1][k]; } for(int j = 1; j <= n; j++) for(int k = j; k <= m; k++) cost[j][k] = query(j, k); } void foo(int gon, int l, int r, int optl, int optr){ if(l > r) return; if(l == r){ int &ans = dp[gon][l]; int &ind = opt[gon][l]; ans = 1e9, ind = -1; for(int j = optl; j <= optr; j++) if(ans > (dp[gon-1][j-1] + cost[j][l])){ ans = dp[gon-1][j-1] + cost[j][l]; ind = j; } return; } int m = (l+r) >> 1; foo(gon, m, m, optl, optr); foo(gon, l, m-1, optl, opt[gon][m]); foo(gon, m+1, r, opt[gon][m], optr); } int solve(int gon){ for(int j = 1; j <= n; j++) dp[1][j] = cost[1][j]; for(int j = 2; j <= gon; j++) foo(j, 1, n, 1, n); return dp[gon][n]; } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); memset(a, 0, sizeof(a)); memset(dp, 1e9, sizeof(dp)); int gon; scanf("%d%d\n",&n ,&gon); m = n;// = 4000; //gon = 10; for(int j = 1; j <= n; j++){ char buffer[8001]; gets(buffer); for(int k = 1; k <= m; k++) a[j][k] = buffer[2*(k - 1)] - '0'; } build(); cout << solve(gon) << endl; return 0; }
run
|
edit
|
history
|
help
0
candies problem
ExceptExpo
OTHER - Two robots
11080 WIP
Test 11(2020)
Divide
ledproject
w1
Hello World - verbose
Dejalo a la Suerte