美文网首页数据结构
「动态规划」练习

「动态规划」练习

作者: 云中翻月 | 来源:发表于2019-03-10 12:48 被阅读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
    

    相关文章

      网友评论

        本文标题:「动态规划」练习

        本文链接:https://www.haomeiwen.com/subject/nerupqtx.html