vijos 1421 更换轮胎 - 前缀和优化dp

xiaoxiao2021-02-27  281

传送门

题解:和上一个题一样

强迫症晚期必须做到O(n)空间

代码:

//vijos 1421 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #define INF (LLONG_MAX/2) #define N 1010 #define lint long long using namespace std; lint dp[2][N],pre[N],suf[N]; int main() { int n,m,c;scanf("%d%d%d",&n,&m,&c); int now=1,last=0; for(int i=0;i<=m+1;i++) pre[i]=suf[i]=INF; for(int i=1;i<=n;i++,swap(now,last)) { for(int j=1;j<=m;j++) { int x;scanf("%d",&x); dp[now][j]=min(dp[last][j],min(pre[j-1],suf[j+1])+c)+x; } for(int j=1;j<=m;j++) pre[j]=min(pre[j-1],dp[now][j]); for(int j=m;j>=1;j--) suf[j]=min(suf[j+1],dp[now][j]); } printf("%lld\n",pre[m]);return 0; }

转载请注明原文地址: https://www.6miu.com/read-8844.html

最新回复(0)