题意:给定一串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; }