poj 3671(DP LIS 暴力)

    xiaoxiao2025-02-14  10

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

    转载请注明原文地址: https://ju.6miu.com/read-1296437.html
    最新回复(0)