题意：给定一串1,2组成的数字，求最少改变多少个数字能使这串数字使其前半部分全为1（或者没有），后半部分全为2（或者没有）。我的方法比较笨，直接枚举1的数量，看看需要进行多少次修改，取最小值即可。比赛后看了别人的代码，虽然大概思路是相同的，但是我的却用时很长，意识到自己之前的方法不太好于是又重新用另一种方法写了一遍。
补充：一年了，无意间再回来看这篇博客，发现这其实是一个明显的DP题LIS，因为只有两个数，所以去年的暴力也是可以过得，枚举1,2的分界。不过还是用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 double eps = 0.00000000000001; int main() { int n; int a[maxn]; int b[maxn]; while(~scanf("%d",&n)) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); int t; int cur = 1; for(int i = 1; i <= n; i++) scanf("%d",&a[i]); for(int i = 1; i <= n; i++) { if(i == 1) { if(a[i] == 2) cur = 2;//用b数组保存每一小段连续出现的1的数量，2的数量。b[1]表示最开始出现的1的数量 b[cur]++;//（若2开头则b[1] = 0）,b[2]表示最开始连续的2的数目，以此类推 continue; } if(a[i] == a[i-1]) b[cur]++; else { b[++cur]++; } } int sum = 0; for(int num1 = 0; num1 <= cur; num1++)//枚举1的数目（枚举的是b数组的下标） { int ans = 0; for(int i = 1; i <= num1; i++)//前num1个中的2全部改成1 { if(i % 2 == 0) ans += b[i]; } for(int i = num1 + 1; i <= cur; i++)//num1以后的1全部改成2 { if(i % 2 == 1) ans += b[i]; } if(!num1) sum = ans; else sum = ans < sum ? ans : sum; } printf("%d\n",sum); } return 0; } 这个耗时太多，也有点麻烦，所以重新写了一种。 #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 main() { int n; while(~scanf("%d",&n)) { int a[maxn], b[maxn], c[maxn]; int one = -1, two = 0; for(int i = 1; i <= n; i++)//正向记录到第i个数字时当前连续出现过的2的数目 { scanf("%d",&c[i]); if(c[i] == 2) two++; a[i] = two; } for(int i = n; i >= 1; i--)//逆向记录到第i个数字时当前连续出现过的1的数目 { if(c[i] == 1) one++; b[i] = one; } int ans = inf; for(int i = 1; i <= n; i++)//枚举1的数目i，第i个数前面出现过的2全部变成1，，第i个数前面出现过的1全部变成2 { ans = min(ans , a[i] + b[i]);//取所有枚举结果的最小值 } printf("%d\n",ans); } return 0; }