C-Cities

live4m題解

#include<bits/stdc++.h>using namespace std;const int N=5050; int f[N][N],a[N]; int n,m; map<int,int> mp; int pre[N]; int dfs(int l,int r) {if(l==r) return 0;if(f[l][r]!=-1) return f[l][r];int &v=f[l][r];v=(r-l+1)-1;if(a[l]==a[r]) v=min(v,dfs(l+1,r-1)+1);elsev=min(v,dfs(l+1,r)+1),v=min(v,dfs(l,r-1)+1);for(int k=pre[r];k>l;k=pre[k]){if(a[l]==a[r])v=min(v,dfs(l,k-1)+dfs(k+1,r));elsev=min(v,dfs(l,k-1)+dfs(k,r)+1);}return v; } int main() {ios::sync_with_stdio(false);cin.tie();cout.tie(0);int Tc;cin>>Tc;while(Tc--){mp.clear();n=0;cin>>m;for(int i=1;i<=m;i++) {int v;cin>>v;if(v!=a[n]) {a[++n]=v;pre[n]=mp[v];mp[v]=n;}}memset(f,-1,sizeof f);cout<<dfs(1,n)<<'\n';}return 0; }

3996. 涂色

AcWing第 20 場周賽 是上面的題的弱化版

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=5005; int n,m; int f[N][N]; int a[N]; int dfs(int l,int r) {if(l==r) return 0;if(f[l][r]!=-1) return f[l][r];if(a[l]==a[r]) f[l][r]=dfs(l+1,r-1)+1;elsef[l][r]=min(dfs(l+1,r),dfs(l,r-1))+1;return f[l][r]; } int main() {m=rd();for(int i=1;i<=m;i++) {int s=rd();if(s!=a[n]) a[++n]=s;}memset(f,-1,sizeof f);printf("%d\n",dfs(1,n));return 0; }```

總結

以上是生活随笔為你收集整理的第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） Cities（区间dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。