【POJ 3666】Making the Grade（简单DP)

本文主要是介绍【POJ 3666】Making the Grade（简单DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先可以明确一个方面，那就是如果将X改成Y，那么Y肯定是这N个数中的某一个（为什么仔细想想）

之后可以得到一个状态转移那就是dp[i][j]代表已经考虑了i位的情况下，结尾为j的最小更改数。

状态转移为dp[i][j] = min(dp[i-1][k] + abs(a[i] - b[j])) 这样的话可以写出一个初步的代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int  INF = 1 << 30;
const int maxn = 2005;
int arr[maxn];
int Hash[maxn],cnt;
int dp[maxn][maxn];
int n;
void Hash_init(){sort(Hash,Hash + cnt);cnt = unique(Hash,Hash + cnt) - Hash;//printf("%d\n",cnt);
}
void solve(){dp[0][0] = 0;for(int i = 1; i < n; i++){for(int j = 0; j < cnt; j++){dp[i][j] = INF;for(int k = 0; k <= j; k++){dp[i][j] = min(dp[i][j],dp[i - 1][k] + abs(Hash[j] - arr[i]));}}}int ans = dp[n - 1][0];for(int i = 1; i < cnt; i++)ans = min(ans,dp[n - 1][i]);printf("%d\n",ans);
}
int main(){while(scanf("%d",&n) != EOF){cnt = 0;for(int i = 0; i < n; i++){scanf("%d",&arr[i]);Hash[cnt++] = arr[i];}Hash_init();solve();}return 0;
}

继续看，这里3个for循环对于上千的数据肯定是不行的，既然这样我们优化，首先我们可以知道每次取min(dp[i - 1][t])就可以，这里t <= j，这里我们用一个数组pre[]来代表这个结果，这样直接去了一层循环，pre[t]每次循环需要更新

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int  INF = 1 << 30;
const int maxn = 2005;
int arr[maxn],pre[maxn];
int Hash[maxn],cnt;
int dp[maxn][maxn];
int n;
void Hash_init(){sort(Hash,Hash + cnt);cnt = unique(Hash,Hash + cnt) - Hash;
}
void solve(){dp[0][0] = 1;for(int i = 1; i < n; i++){for(int j = 0; j < cnt; j++){dp[i][j] = pre[j] + abs(Hash[j] - arr[i]);if(!j)pre[j] = dp[i][j];elsepre[j] = min(pre[j - 1],dp[i][j]);}}int ans = dp[n - 1][0];for(int i = 1; i < cnt; i++)ans = min(ans,dp[n - 1][i]);printf("%d\n",ans);
}
int main(){while(scanf("%d",&n) != EOF){cnt = 0;for(int i = 0; i < n; i++){scanf("%d",&arr[i]);Hash[cnt++] = arr[i];}Hash_init();solve();}return 0;
}

这样已经可以AC了，但是我们还可以利用滚动数组去优化空间

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2005;
int arr[maxn],pre[maxn];
int Hash[maxn],cnt;
int dp[2][maxn];
int n;
void Hash_init(){sort(Hash,Hash + cnt);cnt = unique(Hash,Hash + cnt) - Hash;
}
void solve(){dp[0][0] = 1;int k = 0;for(int i = 1; i < n; i++){for(int j = 0; j < cnt; j++){dp[k][j] = pre[j] + abs(Hash[j] - arr[i]);if(!j)pre[j] = dp[k][j];elsepre[j] = min(pre[j - 1],dp[k][j]);}k ^= 1;}k ^= 1;int ans = dp[k][0];for(int i = 1; i < cnt; i++)ans = min(ans,dp[k][i]);printf("%d\n",ans);
}
int main(){while(scanf("%d",&n) != EOF){cnt = 0;for(int i = 0; i < n; i++){scanf("%d",&arr[i]);Hash[cnt++] = arr[i];}Hash_init();solve();}return 0;
}

恩，就是这样~

这篇关于【POJ 3666】Making the Grade（简单DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---