点击打开链接
题意：给定一串数字，求改变最小的数字使其变成升序或降序排列。暴力是不可能的，写着写着就把自己写晕了。看了他人的思路，使用DP写的，自己也推了一会，虽然是看过别人的思路才会的自己也推出来了，但是还是希望下次靠自己就能推出DP公式吧。其实这是一个LIS（最长上升子序列），只要求出最长LIS的长度，用总数减去就是答案。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<map> #include<vector> #include<cmath> #include<set> using namespace std; typedef long long ll; const int maxn = 30000 + 5; const int inf = 0x3f3f3f3f; const double eps = 0.00000000000001; int a[maxn]; int dp[maxn][4]; int n; int solve(int *a)//dp[i][j]表示从第一位直至将第i位修改为j时为止总共进行了多少次修改 { memset(dp, 0, sizeof(0)); dp[1][1] = dp[1][2] = dp[1][3] = 1;//第一位修改为1,2,3时均需修改一次就行 dp[1][a[1]] = 0; for(int i = 1; i <= n; i++) { if(a[i] == 1) dp[i][1] = dp[i - 1][1];//a[i]本身就是1，不需要进行修改，故等于将第i-1位修改为1时总共进行的修改次数 else dp[i][1] = dp[i - 1][1] + 1;//a[i]不是1时，第i位需要进行一次修改 if(a[i] == 2) dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]);//a[i]本身就是2时不需要修改第i位，故dp[i][2]的值为前一位为1或者为2时总共进行的修改次数（二者取最小） else dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1; if(a[i] == 3) { dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]);//a[i]本身就是3时不需要修改第i位，故dp[i][3]的值为前一位为1或者为2或者为3时总共进行的修改次数（三者取最小） dp[i][3] = min(dp[i][3], dp[i - 1][3]); } else { dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]) + 1; dp[i][3] = min(dp[i][3], dp[i - 1][3] + 1); } } return min(dp[n][1], min(dp[n][2], dp[n][3]));//返回最小值 } int main() { while(~scanf("%d",&n)) { memset(a, 0, sizeof(a)); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } // memset(dp, 0, sizeof(dp)); int sum = solve(a);//求升序 reverse(a + 1, a + 1 + n);//将a翻转后求逆序 sum = min(sum, solve(a)); printf("%d\n",sum); } return 0; }