「动态规划」练习

2019-03-10 本文已影响8人云中翻月

0x5E「动态规划」练习

5E01 乌龟棋
考虑如何表示当前状态，d[x,i,j,k,l]表示目前在x位置，四种牌的使用张数分别为i,j,k,l时的最大分数。发现时间空间复杂度过高，因此考虑优化。
仔细观察后发现，只要知道四种牌的使用张数就能够算出当前位置x=i+2j+3k+4*l+1。因此修改状态定义如下：
状态表示：d[i,j,k,l]表示四种牌的使用张数分别为i,j,k,l时的最大分数
转移方程：
$若\;i>0，d[i,j,k,l]=\max\left\{d[i,j,k,l],d[i-1,j,k,l]+a[i+2*j+3*k+4*l+1]\right\}$
其他牌同理
边界： $d[0,0,0,0]=a[1]$
目标： $d[cnt1,cnt2,cnt3,cnt4],其中\;cnt1,cnt2,cnt3,cnt4\;是四张牌的初始张数$
时间复杂度： $O(40^{4})$
代码如下：（ps：为了简化代码，使用了引用表示d[i,j,k,l]）

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=350+5;
const int maxm=40+5;
const int INF=0x3f3f3f3f;
int d[maxm][maxm][maxm][maxm]={0},cnt1=0,cnt2=0,cnt3=0,cnt4=0,n,m,a[maxn],x;
int main() {
    ios::sync_with_stdio(false);
    //freopen("乌龟棋.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>x;
        if(x==1) cnt1++;
        if(x==2) cnt2++;
        if(x==3) cnt3++;
        if(x==4) cnt4++;
    }
    d[0][0][0][0]=a[1];
    for(int i=0;i<=cnt1;i++){
        for(int j=0;j<=cnt2;j++){
            for(int k=0;k<=cnt3;k++){
                for(int l=0;l<=cnt4;l++){
                    int &temp=d[i][j][k][l];
                    int v=a[i+2*j+3*k+4*l+1];
                    if(i) temp=max(temp,d[i-1][j][k][l]+v);
                    if(j) temp=max(temp,d[i][j-1][k][l]+v);
                    if(k) temp=max(temp,d[i][j][k-1][l]+v);
                    if(l) temp=max(temp,d[i][j][k][l-1]+v);
                }
            }
        }
    }
    cout<<d[cnt1][cnt2][cnt3][cnt4];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5E02 花店橱窗
考虑状态设计，由于每种花要依次放置，所以以当前放置的花为阶段，以花瓶和花为状态建立状态表示。
状态表示：d[i,j]表示当前放到第i种花，到达第j个花瓶的最大美观度
转移方程：
对于第j个花瓶，有两种决策：放花和不放花
不放花的情况
$d[i,j]=\max_{i+1 \leq j\leq v}\left\{d[i,j],d[i,j-1]\right\}$
放花的情况
$d[i,j]=\max_{i-1 \leq k\leq j-1}\left\{d[i,j],d[i-1,k]+a[i,j]\right\}$
边界： $d[0,i]=0,其中\;1\leq i \leq v。其他\;d\;值均为-INF(答案可能是负数)$
目标： $d[f,v]$
时间复杂度： $O(f*v^{2})$
题目还要求记录方案，因此我使用了一个pre1[i,j]和pre2[i,j]记录d[i,j]取到最大值时的上一个状态d[x,y]的两个下标x和y。最后递归输出即可。
代码如下：（ps：和LCIS类似，这题的状态转移方程也有一样的特点，考虑每次随着j的增加 k的范围相对最外层循环只增不减(范围是[i-1,j-1]) 而且每次只增加一个单位。因此可以用变量记录d[i-1][j-1]的取到最优值时j-1的值，从而优化dp。几种方法的具体过程详见代码）

/*

*/
#define method_2
#ifdef method_1
/*
无方案 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn],a[maxn][maxn],f,v;
int main() {
    ios::sync_with_stdio(false);
    //freopen("花店橱窗.in","r",stdin);
    cin>>f>>v;
    for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) cin>>a[i][j];
    memset(d,-INF,sizeof(d)); //注意答案可能是负数 所以要初始化为-INF 而不是0 
    for(int i=0;i<=v;i++) d[0][i]=0;
    for(int i=1;i<=f;i++){ //为了保证放花的顺序 这里第一重循环是循环花数 即阶段 每个阶段放一束花 
        for(int j=i;j<=v;j++){
            if(j-1>=i) d[i][j]=max(d[i][j-1],d[i][j]);
            for(int k=i-1;k<=j-1;k++) d[i][j]=max(d[i][j],d[i-1][k]+a[i][j]);
        }
    }
    cout<<d[f][v];
    return 0;
}
#endif
#ifdef method_2
/*
带方案
考虑每次随着j的增加 k的范围相对最外层循环只增不减(范围是[i-1,j-1]) 而且每次只增加一个单位。因此可以用变量记录d[i-1][j-1]的取到最优值时j-1的值，从而优化dp 
双重循环 优化dp 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn],a[maxn][maxn],pre1[maxn][maxn],pre2[maxn][maxn],f,v;
void print(int f,int v){
    if(pre1[f][v]==0) return;
    print(pre1[f][v],pre2[f][v]);
    cout<<pre2[f][v]<<" ";
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("花店橱窗.in","r",stdin);
    cin>>f>>v;
    for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) cin>>a[i][j];
    memset(d,-INF,sizeof(d)); //注意答案可能是负数 所以要初始化为-INF 而不是0 
    for(int i=0;i<=v;i++) d[0][i]=0;
    for(int i=1;i<=f;i++){
        int k=i-1;
        for(int j=i;j<=v;j++){
            d[i][j]=d[i-1][k]+a[i][j]; 
            pre1[i][j]=i-1;
            pre2[i][j]=k;
            if(d[i-1][j]>d[i-1][k]){
                k=j;
            }
        }
    } 
    int last=0;
    for(int i=f;i<=v;i++){
        if(d[f][i]>d[f][last]){ //method_2不能保证d[f][v]就是最优解 需要循环找一下 目前原因未知 
            last=i;
        }
    }
    cout<<d[f][last]<<endl;
    print(f,last);
    cout<<last;
    return 0;
}
#endif
#ifdef method_3
/*
带方案
三重循环 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn],a[maxn][maxn],pre1[maxn][maxn],pre2[maxn][maxn],f,v;
void print(int f,int v){
    if(pre1[f][v]==0) return;
    print(pre1[f][v],pre2[f][v]);
    cout<<pre2[f][v]<<" ";
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("花店橱窗.in","r",stdin);
    cin>>f>>v;
    for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) cin>>a[i][j];
    memset(d,-INF,sizeof(d)); //注意答案可能是负数 所以要初始化为-INF 而不是0 
    for(int i=0;i<=v;i++) d[0][i]=0;
    for(int i=1;i<=f;i++){
        for(int j=i;j<=v;j++){
            if(j-1>=i){
                if(d[i][j]<d[i][j-1]){
                    d[i][j]=d[i][j-1];
                    pre1[i][j]=i;
                    pre2[i][j]=j-1;
                }
            }
            for(int k=i-1;k<=j-1;k++){
                if(d[i][j]<d[i-1][k]+a[i][j]){
                    d[i][j]=d[i-1][k]+a[i][j];
                    pre1[i][j]=i-1;
                    pre2[i][j]=k;
                }
            }
        }
    }
    cout<<d[f][v]<<endl;
    int last;
    for(int i=f;i<=v;i++){
        if(d[f][i]==d[f][v]){
            last=i;
            break;
        }
    }
    print(f,last);
    cout<<last;
    return 0;
}
#endif

POJ1952 Buy Low Buy Lower
LIS的裸题，第一问的状态转移方程不再赘述，这里讲一下第二问怎么求方案。设[1...i]的最长递减子序列的长度为d[i]，对应方案数为f[i]，则：
$若a[j]>a[i]\;且\;d[i]==d[j]+1,则 f[i]+=f[j] 其中\;0 \leq j \leq i-1$
但需要注意的是题目中不同方案的定义：两个相同的子序列即使选出的位置不一样，也属于一样的子序列，所以j需要倒序循环，具体原理和反例见代码

/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],d[maxn],f[maxn],ans,ans1;
int main() {
    ios::sync_with_stdio(false);
    //freopen("Buy Low Buy Lower.in","r",stdin);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    f[0]=1;
    a[0]=INF;
    for(int i=1; i<=n; i++) {
        d[i]=1;
        for(int j=0; j<i; j++) {
            if(a[j]>a[i]) d[i]=max(d[i],d[j]+1);
        }
        /*
        //不能这么写 反例
        5
        3 2 3 1 1 
        需要输出 3 1
        而不是3 2 
        因为两个最长递减子序列都是3 2 1 所以只能算成一个 
        for(int j=0;j<i;j++){
            if(a[j]>a[i]&&d[i]==d[j]+1) f[i]+=f[j];
        }
        */
        ans=max(ans,d[i]);
    }
    for(int i=1; i<=n; i++) {
        for(int j=i-1; j>=0; j--) { //倒序循环  不能够顺序进行 反例在上面 
            if(a[j]>a[i]&&d[i]==d[j]+1) f[i]+=f[j];
            if(a[i]==a[j]) break; //相同就break 
        }
        cout<<f[i]<<" "; 
    }
    cout<<endl;
    for(int i=1; i<=n; i++) {
//      cout<<f[i]<<" ";
        if(d[i]==ans) {
            ans1+=f[i];
//          cout<<i<<" "<<f[i]<<endl;
        }
    }
//  cout<<endl;
    cout<<ans<<" "<<ans1;
    return 0;
}

POJ1934 Trip
求LCS的过程不再赘述，这里讲一下怎么求方案。
预处理出如下数组
d[i][j]表示s1[1...i]和s2[1...j]的LCS
f[i][j]表示s1[1...i]中的j+'a'最后一次出现的位置
g[i][j]表示s2[1...i]中的j+'a'最后一次出现的位置
然后从最后的状态向前dfs，每次尝试是否选取当前位的字母即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=1000+5;
const int maxl=26+5;
const int INF=0x3f3f3f3f;
int n,m,d[maxn][maxn],f[maxn][maxl],g[maxn][maxl],tot=0;
//d[i][j]表示s1[1...i]和s2[1...j]的LCS
//f[i][j]表示s1[1...i]中的j+'a'最后一次出现的位置
//g[i][j]表示s2[1...i]中的j+'a'最后一次出现的位置
string s1,s2,s[maxm];
void dfs(int len1,int len2,int len,string now) {
    if(!len) {
        s[++tot]=now;
        return;
    }
    if(!len1||!len2) return;
    for(int i=0; i<=25; i++) {
        int pos1=f[len1][i],pos2=g[len2][i];
        if(d[pos1][pos2]!=len) continue;
        dfs(pos1-1,pos2-1,len-1,char(i+'a')+now);//注意不能写成dfs(pos1,pos2,len-1,now+char(i+'a'));
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Trip.in","r",stdin);
    cin>>s1>>s2;
    s1=' '+s1,s2=' '+s2;
    n=s1.length()-1,m=s2.length()-1;
//  for(int i=1;i<=n;i++) cout<<s1[i];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(s1[i]==s2[j]) d[i][j]=max(d[i][j],d[i-1][j-1]+1);
            else d[i][j]=max(d[i][j-1],d[i-1][j]);
        }
    }
//  cout<<d[n][m];
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=25; j++) {
            if(s1[i]==j+'a') f[i][j]=i;
            else f[i][j]=f[i-1][j];
        }
    }
    for(int i=1; i<=m; i++) {
        for(int j=0; j<=25; j++) {
            if(s2[i]==j+'a') g[i][j]=i;
            else g[i][j]=g[i-1][j];
        }
    }
    dfs(n,m,d[n][m],"");
    sort(s+1,s+tot+1);
    for(int i=1; i<=tot; i++) cout<<s[i]<<endl;
    return 0;
}
#endif

POJ1722 Substract
假设只有两个数a,b，则只可能产生a-b
假设只有三个数a,b,c，则可能产生a-b-c和a-b+c
假设只有四个数a,b,c，则可能产生a-b-c+d、a-b+c-d、a-b-c-d、a-b+c+d
以此类推，第一个数前一定是'+'号，第二个数前一定是'-'号，其他的数字都可以通过一定的顺序改变前面的符号。
因此，问题等价于求在n个数前面使用加减号使得结果为t的方案，其中第一个数前一定是'+'号，第二个数前一定是'-'号。
因此做出如下状态定义：
状态表示：d[i,j]表示前i个数计算后达到j时，第i个数前的符号。d[i,j]=1表示'+'号，d[i,j]=-1表示'-'号，d[i,j]=0表示未更新或无法达到。
转移方程：
对于第i个数字，有两种决策：前面放'+'号或者'-'号
$若d[i-1,j]!=0,d[i,j+a[i]]=1,d[i,j-a[i]=-1$
边界： $d[1,a[1]]=1,d[2,a[1]-a[2]]=-1$
目标： $d[n,t]$
时间复杂度： $O(n*t)$
这题还有两个注意的地方：
1 由于j可能为负数，所以要做坐标平移
2 考虑输出方案，因为有SPJ，所以可以构造一组合法的解：先去处理所有的加号，相当于把所有的加号都挪去了原来a3的位置，这样最后处理减号的时候，减a2就可以负负得正了。然后处理减号，把所有的减号都挪到了原来a2的位置，给a1来减。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
https://www.cnblogs.com/wyboooo/p/9775701.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int base=10100+5;
const int INF=0x3f3f3f3f;
int n,t,a[maxn],d[maxn][base*2+200],ans[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("Substract.in","r",stdin);
    cin>>n>>t;
    t+=base;
    for(int i=1;i<=n;i++) cin>>a[i];
    d[1][a[1]+base]=1;
    d[2][a[1]-a[2]+base]=-1;
    for(int i=3;i<=n;i++){
        for(int j=-10000+base;j<=10000+base;j++){
            if(d[i-1][j]){
                d[i][j+a[i]]=1,d[i][j-a[i]]=-1;
            }
        }
    }
    for(int i=n;i>=2;i--){
        ans[i]=d[i][t];
        if(ans[i]==-1){
            t+=a[i];
        }
        if(ans[i]==1){
            t-=a[i];
        }
    }
    int cnt=0;
    for(int i=2;i<=n;i++){ //先处理加号（这里减一次 后面的循环再减一次 就成了加号） 
        if(ans[i]==1){
            cout<<i-cnt-1<<endl;
            cnt++;
        }
    }
    for(int i=2;i<=n;i++){
        if(ans[i]==-1){
            cout<<1<<endl;
        }
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1187 陨石的秘密
题解链接
https://blog.csdn.net/flying_stones_sure/article/details/7954114
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
https://blog.csdn.net/flying_stones_sure/article/details/7954114
dp核心：为了防止一个序列被重复计数，用http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5302%20%E9%87%91%E5%AD%97%E5%A1%94相同的方法
即每次枚举括号的时候 依次枚举最靠左边外面的括号是()[]还是{}这样在记忆化搜索的时候就不会有重复或遗漏
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxl=15+5;
const int maxd=30+5;
const int mod=11380;
const int INF=0x3f3f3f3f;
int l1,l2,l3,d,f[maxl][maxl][maxl][maxd];
int dfs(int l1,int l2,int l3,int d) {
    if((!l1)&&(!l2)&&(!l3)) {
        return f[l1][l2][l3][d]=1;
    }
    if(!d) {
        return f[l1][l2][l3][d]=0;
    }
    if(f[l1][l2][l3][d]) {
        return f[l1][l2][l3][d];
    }
    int res=0;
    for(int i=0; i<=l3; i++) {
        if(i) res=(res+dfs(0,0,i-1,d-1)*dfs(l1,l2,l3-i,d)%mod)%mod;
        for(int j=0; j<=l2; j++) {
            if(j) res=(res+dfs(0,j-1,i,d-1)*dfs(l1,l2-j,l3-i,d)%mod)%mod;
            for(int k=0; k<=l1; k++) {
                if(k) res=(res+dfs(k-1,j,i,d-1)*dfs(l1-k,l2-j,l3-i,d)%mod)%mod;
            }
        }
    }
    return f[l1][l2][l3][d]=res;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("陨石的秘密.in","r",stdin);
    cin>>l1>>l2>>l3>>d;
    if(d) cout<<(dfs(l1,l2,l3,d)-dfs(l1,l2,l3,d-1)+mod)%mod;
    else cout<<dfs(l1,l2,l3,d)%mod;
    //不能写成 else cout<<0; 因为dfs(0,0,0,0)=1 
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5E07 划分大理石
多重背包，但由于只是判断可行性，所以直接照搬POJ1742 Coins就行了。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
可行性dp多重背包 不需要二进制拆分或者单调队列优化
方法参见coin 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=6+5;
const int maxm=200000+5;
const int INF=0x3f3f3f3f;
int a[maxn],f[maxm],used[maxm];
int main() {
    ios::sync_with_stdio(false);
//  freopen("划分大理石.in","r",stdin);
    while(1) {
        int flag=0,sum=0;
        for(int i=1; i<=6; i++) {
            cin>>a[i];
            sum+=a[i]*i; 
            if(a[i]!=0) flag=1;
        }
        if(!flag) break;
        if(sum&1){ //注意这里要特判 
            cout<<"Can't"<<endl;
            continue;
        }
        sum/=2;
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=6;i++){
            memset(used,0,sizeof(used));
            for(int j=i;j<=sum;j++){
                if(!f[j]&&f[j-i]&&used[j-i]<a[i]){
                    f[j]=1,used[j]=used[j-i]+1;
                }
            }
        }
        if(f[sum]) cout<<"Can"<<endl;
        else cout<<"Can't"<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ2176 Folding
区间DP，讨论两种决策，分割区间和将区间压缩，分别转移即可，具体到实现上，可以借助一个struct来记录[i...j]的最短长度len和对应方案s。利用sprintf和strcpy，strcat转移即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n;
string s;
struct node{
    char s[maxn]; //记录方案 
    int len;
}f[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("Folding.in","r",stdin);
    cin>>s,s=' '+s,n=s.length();
    for(int i=1;i<=n;i++){
        f[i][i].len=1,f[i][i].s[0]=s[i];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            f[i][j].len=INF;
            for(int k=1;k<=len/2;k++){ //贪心原则 让压缩后的子串（除去数字和括号）尽量短 因此从小到大枚举压缩长度
                if(len%k) continue;
                int l=i,r=i+k;
                while(r<=j&&s[l++]==s[r]) r++;
                if(r>j){ //可以完全填充[i,j] 
                    sprintf(f[i][j].s,"%d",len/k);
                    strcat(f[i][j].s,"(");
                    strcat(f[i][j].s,f[i][i+k-1].s);
                    strcat(f[i][j].s,")");
                    f[i][j].len=strlen(f[i][j].s);
                    break;//贪心原则 让压缩后的子串（除去数字和括号）尽量短 
                }
            }
            for(int k=i;k<j;k++){
                if(f[i][j].len>f[i][k].len+f[k+1][j].len){
                    f[i][j].len=f[i][k].len+f[k+1][j].len;
                    strcpy(f[i][j].s,f[i][k].s);
                    strcat(f[i][j].s,f[k+1][j].s);
                }
            }
        }
    }
    cout<<f[1][n].s;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5E09 能量项链
区间DP，具体细节详见代码。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],ans=0,d[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("能量项链.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
    for(int len=2;len<=n;len++){
        for(int i=1;i<=2*n-len+1;i++){
            int j=len+i-1;
            for(int k=i;k<j;k++){
                d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]);  
                //a[i]*a[k+1]*a[j+1]的解释
                /*
                a[]={0,3,4,5,6,7,8} i=1,j=5,k=2 a[i]=3,a[k]=4,a[k+1]=5,a[j]=7
                则此时a分为两段[3,4]和[5,6,7,8]
                相当于两端珠子(3,4)(4,5)和(5,6)(6,7)(7,8)
                分别合并后两端珠子变成(3,5)和(5,8) 
                合并后的珠子为(3,8) 这一次合并放出的能量是3*5*8=a[1]*a[3]*a[6]=a[i]*a[k+1]*a[j+1] 
                */ 
            }
        }
    }
    for(int i=1;i<=n+1;i++){
        ans=max(ans,d[i][i+n-1]);
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1191 棋盘分割
化简均方差公式
$方差\;^{2}\;=\;\frac{1}{n}\sum_{i=1}^{矩形块数\;n}(x_{i}-\bar{x}^{2})\;=\;\frac{1}{n}\sum_{i=1}^{矩形块数\;n}(x_{i}^{2})-\bar{x}^{2}$
因此，我们发现， $\bar{x}^2$ 为定值，所以只考虑计算 $\sum_{i=1}^{矩形块数\;n}(x_{i}^{2})$ ，其中 $x_{i}$ 为第i个矩形的元素和。
因此用一个五维dp数组进行递推即可，代码里有博客链接，那里有关于状态定义，状态转移方程和初值的详解。
代码如下

/*
注意题目要求 ——使各矩形棋盘总分的均方差最小
公式中xi为第i块矩形棋盘的总分 而不是某个矩形的第i个元素！
因此在dp的时候 dp初态是矩形各个元素的和的平方 而不是平方和！
https://www.cnblogs.com/scau20110726/archive/2013/02/27/2936050.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+2;
const int maxl=8+2;
const int INF=0x3f3f3f3f;
double d[maxn][maxl][maxl][maxl][maxl],s[maxl][maxl];
int n;
double cal(int i,int j,int k,int l) {
    double ans=s[k][l]-s[k][j-1]-s[i-1][l]+s[i-1][j-1];
    return ans*ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("棋盘分割.in","r",stdin);
    scanf("%d",&n);
    for(int i=1; i<=8; i++) {
        for(int j=1; j<=8; j++) {
            scanf("%lf",&s[i][j]);
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    for(int m=1; m<=n; m++)
        for(int i=1; i<=8; i++) {
            for(int j=1; j<=8; j++) {
                for(int k=i; k<=8; k++) {
                    for(int l=j; l<=8; l++) {
                        if(m==1) d[1][i][j][k][l]=cal(i,j,k,l);
                        else d[m][i][j][k][l]=1<<30;
                    }
                }
            }
        }
//  printf("%lf\n",cal(1,2,1,2));
    for(int m=2; m<=n; m++) {
        for(int i=1; i<=8; i++) {
            for(int j=1; j<=8; j++) {
                for(int k=i; k<=8; k++) {
                    for(int l=j; l<=8; l++) {
                        double &temp=d[m][i][j][k][l];
                        for(int x1=i; x1<k; x1++) { //注意x1的范围  
                            temp=min(temp,d[m-1][i][j][x1][l]+cal(x1+1,j,k,l));
                            temp=min(temp,d[m-1][x1+1][j][k][l]+cal(i,j,x1,l));
                            //由于存在顺序问题 所以要选一个作为不会再切的矩形 
                            //如果这里只有一行 会wa 
                        }
                        for(int x2=j; x2<l; x2++) {
                            temp=min(temp,d[m-1][i][j][k][x2]+cal(i,x2+1,k,l));
                            temp=min(temp,d[m-1][i][x2+1][k][l]+cal(i,j,k,x2));
                        }
                    }
                }
            }
        }
    }
    printf("%.3lf",sqrt(d[n][1][1][8][8]/n-(s[8][8]/n)*(s[8][8]/n)));
    return 0;
}

POJ1390 Blocks
首先用一个结构体，来记录一个个方块组的长度和颜色。
显然单个的一个方块组可以视为一个长度为1的区间，可以作为区间dp的边界。
之后考虑状态定义：
如果只是用状态d[i,j]来描述消去方块i到方块j获得的分数是无法形成递推关系的。因为在这个时候对于最右边的大块有两种选择，一是直接消去，二是将其与左边某个大块合并删除。而对于选择二来说，删去未必是最有方案，也许还应该与左边的某方块合并后消去。所以只有两个参数是无法准确描述状态并形成递推关系的。
因此附加一个参数来维护状态：
d[l,r,len]表示消去方块组l至r，同时r右边与r同色的方块长度（也称之为个数）为len。
此时递推关系:
直接消去r： $d[l,r,len]=d[l,r-1,0]+(b[r].l+len)*(b[r].l+len)$
将j与左边某个方块k合并： $d[l,r,len]=d[k+1,r-1,0]+d[l,k,b[r].l+len]$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
https://blog.csdn.net/qq_29169749/article/details/52202149
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn][maxn],n,a[maxn],t,kase=0,cnt;
struct Segment{
    int c,l;
}b[maxn];
int dfs(int l,int r,int len){
    if(l>r) return 0;
    if(l==r) return (b[l].l+len)*(b[l].l+len);
    if(d[l][r][len]!=-1) return d[l][r][len];
    int ans=dfs(l,r-1,0)+(b[r].l+len)*(b[r].l+len);
    for(int k=l;k<r;k++){
        if(b[r].c==b[k].c){
            ans=max(ans,dfs(k+1,r-1,0)+dfs(l,k,b[r].l+len));
        }
    }
    return d[l][r][len]=ans;
} 
int main() {
    ios::sync_with_stdio(false);
    //freopen("Blocks.in","r",stdin);
    cin>>t;
    while(t--){
        cout<<"Case "<<++kase<<": ";
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        memset(d,-1,sizeof(d));
        cnt=1;
        for(int i=1;i<=n;i++){
            if(a[i]==a[i-1]){
                b[cnt].l++;
            }
            else{
                b[++cnt].c=a[i];
                b[cnt].l=1;
            }
        }
        cout<<dfs(1,cnt,0)<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1463 Strategic game
很基础的树形dp，每个节点有两个状态，跑一次dfs即可。
但是需要注意的是，这里要求的是看守所有的“边”。也就是说，每条边至少有一个端点存在守卫，因此每个点状态只可能是如下两个状态之一：该节点放置守卫来守卫这个点到其子节点的边，或者该节点不放置守卫，但靠在所有子节点放置守卫来守卫这个点到其子节点的边。
但如果是要守卫树上的所有的“点”，那么就不能做这样简单的状态定义了。因为每个点可以有三种状态：被父亲守卫，被自己守卫，被儿子守卫。具体转移方程参见vijos 1144小胖守皇宫。
本题代码如下

/*

*/
#define method_1
#ifdef method_1
/*
和vijos 1144不同 那道题目要求守卫所有点 因此每个点有三种守卫情况：被自己守卫 被儿子守卫 被父亲守卫 所以状态分三种
换句话说 就是会出现某些边不会被覆盖的情况 反例见method_2 
https://www.cnblogs.com/linda-fcj/p/7206257.html

但是这道题目要求的是 守卫所有边 每条边有两个端点 因此只有两种状态：被父端点守卫 被子端点守卫
因此设f[x][0]表示守卫以x节点为根的子树 x节点不放置士兵的最小代价
f[x][1]表示守卫以x节点为根的子树 x节点放置士兵的最小代价
转移一下就行了
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1500+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][2],deg[maxn];
vector<int>son[maxn];
void dfs(int x) { //flag=0 靠自己保护 flag=1 靠儿子保护
    f[x][0]=0,f[x][1]=1;
    for(int i=0; i<son[x].size(); i++) {
        int y=son[x][i];
        dfs(y);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][0],f[y][1]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Strategic game.in","r",stdin);
    while(~scanf("%d",&n)) {
        memset(deg,0,sizeof(deg));
        for(int i=0; i<=n-1; i++) son[i].clear();
        int now,num,temp;
        for(int i=0; i<=n-1; i++) {
            scanf("%d:(%d)",&now,&num);
            for(int j=0; j<=num-1; j++) {
                scanf("%d",&temp);
                son[now].push_back(temp);
                deg[temp]++;
//              son[temp].push_back(now);
            }
        }
        for(int i=0; i<=n-1; i++) {
            if(!deg[i]) {
                dfs(i);
                cout<<min(f[i][0],f[i][1])<<endl;
                break;
            }
        }
    }
    return 0;
}
#endif
#ifdef method_2
/*
魔改后的vijos 1144的代码 只过了两个点
反例如下 
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 10 0
6 5 0
应该选择3 4 5 6四个点 得到答案24
但是这个程序会输出25
原因在于 最后方案下 1->2的边两端都没有被覆盖
但是这时 所有顶点都是被覆盖到的 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1500+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][2],deg[maxn],a[maxn];
vector<int>son[maxn];
void dfs(int x) { //flag=0 靠自己保护 flag=1 靠儿子保护
    f[x][0]=0,f[x][1]=a[x];
    for(int i=0; i<son[x].size(); i++) {
        int y=son[x][i];
        dfs(y);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][0],f[y][1]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Strategic game.in","r",stdin);
    scanf("%d",&n);
    int pos,now,num,temp;
    for(int i=1; i<=n; i++) {
        scanf("%d",&pos);
        scanf("%d%d",&a[pos],&num);
        for(int j=0; j<=num-1; j++) {
            scanf("%d",&temp);
            son[pos].push_back(temp);
            deg[temp]++;
//          son[temp].push_back(now);
        }
    }
    for(int i=1; i<=n; i++) {
        if(!deg[i]) {
            dfs(i);
            cout<<min(f[i][0],f[i][1])<<endl;
            break;
        }
    }

    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

「动态规划」练习

0x5E「动态规划」练习

猜你喜欢

热点阅读