入门dp（续更）

问题 H: 【动态规划】fstring字符串

时间限制: 1 Sec 内存限制: 64 MB
提交: 39 解决: 13
[提交] [状态] [命题人:外部导入]

题目描述

一个只包含A，B，C三种字符的字符串，如果其中有连续的3个由A，B，C各一个组成的子串，则称这个字符串为fstring字符串。
例如：BAACAACCBAAA就是一个fstring字符串，而AABBCCAABB则不是。
你的任务是计算只包含A，B，C三种字符且长度为n的这种字符串有多少个不是fstring字符串。

输入

一个整数n(l≤n≤30)。

输出

一个整数。

样例输入

样例输出

提示

另一组数据输入2输出9

这个是网易的试题，要求连续三个字符不是ABC的组合，一个可行的思路是——

f[i]表示长度i的字符串的可行方案。

假设该判断第n个字符了，那么决定这个字符的是第n-1，n-2个字符，

如果n-1，n-2相同，

那么f[i-1]必然等于f[i-2]，n可以取任意一个字符，所以f[i]=3*f[i-1]。

如果不相同，那么n取n-1，n-2中的一个，也就是f[i]=(f[i-1]-f[i-2])*2。

综上，f[i]=(f[i-1]-f[i-2])*2+f[i-1]*3。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll a[maxn];
int main()
{
    int n;
    cin>>n;
    a[1]=3;
    a[2]=9;
    for(int i=3;i<=n;i++)
    {
        a[i]=3*a[i-2]+2*(a[i-1]-a[i-2]);
    }
    cout<<a[n]<<endl;
    return 0;
}

View Code

问题 I: 【动态规划】桐桐的爬山计划

时间限制: 1 Sec 内存限制: 64 MB
提交: 9 解决: 3
[提交] [状态] [命题人:外部导入]

题目描述

桐桐一直有个梦想，很希望像“蜘蛛人”罗伯特一样飞檐走壁。为了达成这个梦想，桐桐每天都辛勤练习攀爬。练习的出发点与终点都是在地上面。给出一个数列，代表她每次移动的距离。这个移动可以向上，也可以向下。但是不可能到达地下面去的。而她做练习使用的建筑物总是比她到达过的最高位置高2米。现在我们希望这个建筑物的高度越小越好。
如：20 20 20 20
如果是上，上，下，下的话，这个建筑物就要42米高，如果是上，下，上，下，就只要22米高。
当然有些数列是无解的，例如：3421645。

输入

第1行输入n(n≤l00)，代表有n个爬行距离；
第2行输入n个爬行距离（均为整数），这些爬行距离的总和不超过10000。

输出

如果有解，则输出最小的高度；
否则输出’IMPOSSIBLE’。

样例输入

4
20 20 20 20

样例输出

这个题的思路并不显然，翻了翻题解加上思考才算搞定。

用f[i][j]表示第i次爬行，且当前处于高度j时到达过的最大高度

对于每一个爬行距离tmp，从0到最大值之间查找由i-1转移的状态，也即

f[i][j]——>f[i-1][j+tmp] 或者f[i-1][j-tmp]

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define MAXN 101
 
using namespace std;
 
int n;
int a[MAXN][10001]; //达到过的最高高度
// 一维： 第几次爬行
// 二维： 目前达到的高度
 
int main()
{
    scanf("%d", &n);
    int maxnow = 0;
    for(register int i = 1, tmp; i <= n; i++)
    {
        scanf("%d", &tmp);
        maxnow += tmp;
        if(i == 1) a[1][tmp] = tmp;
        else for(register int j = 0; j <= maxnow; j++)
            {
                if((j - tmp < 0 || !a[i - 1][max(0, j - tmp)]) && (j + tmp > maxnow || !a[i - 1][min(maxnow, j + tmp)]))
                    continue;
                if(j - tmp < 0 || !a[i - 1][max(0, j - tmp)])
                    a[i][j] = max(j, a[i - 1][j + tmp]);
                else if(j + tmp > maxnow || !a[i - 1][j + tmp])
                    a[i][j] = max(j, a[i - 1][j - tmp]);
                else
                    a[i][j] = max(j, min(a[i - 1][j - tmp],a[i - 1][j + tmp]));
            }
    }
    a[n][0] ? printf("%d", a[n][0] + 2) : puts("IMPOSSIBLE");
    return 0;
}

View Code

问题 J: 【动态规划】多米诺骨牌问题

时间限制: 1 Sec 内存限制: 128 MB
提交: 27 解决: 6
[提交] [状态] [命题人:admin]

题目描述

有一种多米诺骨牌是平面的，其正面被分成上下两个部分，每一部分的表面或者为空，或者被标上1至6个点。现在有一行多米诺骨牌排列在桌面上，如下图所示：

顶行（上行）骨牌的点数之和为6+1+1+1=9；底行（下行）骨牌的点数之和为1+5+3+2=11。顶行和底行的差值是2，这个差值是上下两行点数之和的差的绝对值。每个多米诺骨牌都可以上下翻转倒置交换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需要翻转最后一个骨牌，就可以使得顶行和底行的差值为0。所以这个例子的答案为1。

输入

输入的第1行是一个整数n（1<=n<=1000），表示有n个多米诺骨牌在桌面上排成一行。接下来总共有n行，每行包含两个整数 a，b（0<=a,b<=6，中间用空格分开）。第i+1行的a，b分别表示第i个多米诺骨牌的上部和下部的点数（0表示空）。

输出

输出只有一个整数。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。

样例输入

样例输出

1
可以当成01背包问题解决，翻与不翻对应选与不选两种状态，这样思路就很清晰了

#include <bits/stdc++.h>
 
using namespace std;
int a[1005],b[1005],dp[6010];
const int  inf=0x3f3f3f3f;
int main()
{
    int n;
    scanf("%d",&n);
    int s=0,m=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        s+=max(a[i],b[i]);
        m+=a[i]+b[i];
    }
    memset(dp,inf,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=s;j>=0;j--)
        {
            int ans=inf;
            if(j>=a[i])
            {
                ans=dp[j-a[i]];
            }
            if(j>=b[i])
            {
                ans=min(dp[j-b[i]]+1,ans);
            }
            dp[j]=ans;
        }
    }
    int k=inf;
    for(int i=m>>1;i>=0;i--)
    {
        k=min(dp[i],dp[m-i]);
        if(k<inf)
        {
            printf("%d
",k);
            return 0;
        }
    }
    return 0;
}

View Code