网上书店网站建设毕业设计范文,网站管理制度建设的情况,桂林网站定制,网站说明怎么写HDU2476 做法#xff1a; 先想到用\(f[i]\)表示A的前i个字符变成B的最少涂得次数#xff0c;不难写出方程#xff0c;当\(A[i]≠B[i], f[i] max(f[j-1]cost[j][i])\), 当\(A[i]B[i]\)时#xff0c;\(f[i]f[j-1]\) , \(cost[i][j]\) 表示将i到j涂成和B一样的最少的次数。现… HDU2476 做法 先想到用\(f[i]\)表示A的前i个字符变成B的最少涂得次数不难写出方程当\(A[i]≠B[i], f[i] max(f[j-1]cost[j][i])\), 当\(A[i]B[i]\)时\(f[i]f[j-1]\) , \(cost[i][j]\) 表示将i到j涂成和B一样的最少的次数。现在的问题时如何求出 \(cost[i][j]\)可以利用区间dp解决。一开始我的思路是将相邻相同的B串中相邻的同种字母压在一起然后如果\(B[l]B[r]\)\(cost[l][r] cost[l1][r-1]\),否则 另一种转移就是枚举中间的位置\(cost[l][r] min(cost[l][k-1]cost[k][r])\)因为相邻的元素一定不同所以应该不会错。需要查询时我就二分出那个位置被压在哪个压缩后的位置然后正常的做第二次dp就行了。。。然而wa了。。。可能有问题没查出来吧。。正解的不需要压缩串直接 \(cost[l][r] cost[l1][r]1\)枚举中间位置转移时如果两个串的开头相同则这个位置在之前涂过就不涂了。#include cstdio
#include algorithm
#include cstring
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
const int N 200 7;
const int inf 0x3f3f3f3f;
typedef long long ll;
using namespace std;
char A[N],B[N],v[N];
int n,dp[N][N],f[N],cc,num[N];
void init_dp() {rep(i,1,n)rep(j,i,n)dp[i][j]j-i1;rep(len,1,n) {rep(l,1,n-len1) {int r l len - 1;dp[l][r] dp[l1][r] 1;rep(k,l1,r)if(B[l]B[k]){dp[l][r] min(dp[l][r],dp[l1][k]dp[k1][r]);}}}
}int main() {//freopen(in.txt,r,stdin);while(~scanf( %s %s,A1,B1)) {n strlen(A1);init_dp();rep(i,1,n) f[i] dp[1][i];rep(i,1,n){if(A[i]B[i]) f[i] f[i-1];else {rep(j,1,i-1) f[i] min(f[i],f[j]dp[j1][i]);}}printf(%d\n,f[n]);}return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9438638.html
