首页 > 代码库 > HDU 4960 Another OCD Patient 区间dp
HDU 4960 Another OCD Patient 区间dp
区间dp。。
T^T一直感觉是n^3,看了题解看来是数据水了么。。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string.h> #define ll long long #define inf 1e8 inline int min(int a, int b){return a<b?a:b;} inline void rdl(ll &n){ n = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') n *= 10, n += (c - '0'),c = getchar(); } inline void rd(int &n){ n = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') n *= 10, n += (c - '0'),c = getchar(); } #define N 5005 int dp[N][N], cost[N]; ll sum[N], a[N]; int n; int dfs(int l, int r){ if(dp[l][r] != -1)return dp[l][r]; if(l < 1 || r > n)return dp[l][r] = inf; if(sum[l] != sum[n] - sum[r-1])return inf; int s = l, t = r; int ans = inf; while(1 <= s && t <= n) { if(sum[l] - sum[s-1] == sum[t] - sum[r-1]) { int tmp = cost[l-s+1] + cost[t-r+1]; tmp += dfs(s-1, t+1); ans = min(ans, tmp); if(s>=2)s--; else t++; } else if(sum[l] - sum[s-1] > sum[t] - sum[r-1]) t++; else if(sum[l] - sum[s-1] < sum[t] - sum[r-1]) s--; } return dp[l][r] = ans; } int main(){ int i, j, T, k; while(scanf("%d",&n), n){ sum[0] = sum[n+1] = 0; for(i = 1; i <= n; i++)rdl(a[i]), sum[i] = sum[i-1] + a[i]; for(i = 1; i <= n; i++)rd(cost[i]); memset(dp, -1, sizeof dp); dp[0][n+1] = 0; int ans = cost[n]; for(i = 1; i < n; i++) ans = min(ans, dfs(i,i+1)); for(i = 2; i < n; i++) ans = min(ans, dfs(i-1,i+1)); int s = 1, t = n; while( s < t){ if(sum[s] == sum[n] - sum[t-1]) { ans = min(ans, dfs(s,t) + cost[t-s-1]); s++; } else if(sum[s] < sum[n] - sum[t-1]) s++; else t--; } printf("%d\n", ans); } return 0; } /* 5 27 9 9 9 27 0 1000 1000 1 1000 5 27 9 8 10 27 0 1000 1000 1 1000 5 27 9 8 10 27 0 1000 1 1000 1000 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。