文章目录

Codeforces Round #538 (Div. 2)D. Flood Fill

枚举起点进行dp


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 5000+10;

int dp[maxn][maxn];
int a[maxn];
int main(void)
{
    int n;cin>>n;
    for(int i = 1;i <= n; ++i)
        cin>>a[i];
    n = unique(a+1,a+n+1)-a-1;
    for(int i = n;i >= 1; --i){
        for(int j = i+1;j <= n; ++j){
            dp[i][j] = min(dp[i+1][j]+1,dp[i][j-1]+1);
            if(a[i] == a[j])
                dp[i][j] = min(dp[i+1][j-1]+1,dp[i][j]);
        }
    }
    cout<<dp[1][n]<<endl;
    

   return 0;
            
}

Educational Codeforces Round 61 (Rated for Div. 2)F - Clear the String &&BZOJ 1260


#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
const int MAXN = 505;
int dp[MAXN][MAXN],n;
char s[MAXN];
int main()
{
    cin>>n;
    scanf("%s",s+1);
    for(int i = 1;i <= n; ++i) dp[i][i] = 1;
    for(int len = 2; len <= n; ++len){
        for(int l = 1,r = len;r <= n; ++l,++r){
            if(s[l] == s[r]) dp[l][r] = dp[l+1][r-1] + 1;
            else dp[l][r] = min(dp[l+1][r],dp[l][r-1]) + 1;
            for(int k = l;k <= r; ++k)
                dp[l][r] = min(dp[l][r],dp[l][k]+dp[k][r]-1);
        }
    }
    cout<<dp[1][n];
    return 0;
}