主要的学习了一下dp和背包的问题，背包的问题也是用动态规划的问题来解答的，所以主要还是学的动态规划，关于动态规划的内容就不再多说了，关于背包问题一共学习了四种类型的背包问题，分别是01背包、完全背包、多重背包和分组背包问题，背包问题基本上都差不多得变换思路来求解不同类型的题型。

关于动态规划所看的例题：

题意：给出N个字符串，所有字符串的连续回文子串构成一个多重集合S，求S中是否存在恰好K个串，使它们的长度之和为L

题解：先用manacher计算出每种长度回文串出现的个数。在将长度视为物品跑一个多重背包即可。关于这里的背包，我们可以设f[i][j]为一个bool滚动数组，表示构造长度为i的串用了j个子串能不能成立。manacher算法是求解一个字符串的最长回文子串长度的问题，具体细节就不详细说了，把这个题的代码放一下

#include 
#include 
#include 
using namespace std;
const int N = 128;
const char mid_c = '$';
const char side_c = '@';
int n, k, l;
char s[N][N];
char s2[N << 1];
int len, r[N][N << 1];
void prepare(char s1[]) {
    len = 0;
    s2[len++] = side_c;
    s2[len++] = mid_c;
    int n = strlen(s1);
    for (int i = 0; i < n; ++i) {
        s2[len++] = s1[i];
        s2[len++] = mid_c;
    }
    s2[len + 1] = '';
}
void Manacher(char s1[], int id) {
    prepare(s1);
    memset(r[id], 0, sizeof(r[id]));
    int mid = 0, p = 0;
    for (int i = 0; i < len; ++i) {
        int x;
        if (p < i)x = 1;
        else x = min(p - i, r[id][2 * mid - i]);
        while (s2[i - x] == s2[i + x]) ++x;
        if (i + x > p) {
            p = i + x;
            mid = i;
        }
        r[id][i] = x;
    }
}
int cnt[N], dp[N][N];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(cnt, 0, sizeof(cnt));
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d", &n, &k, &l);
        for (int i = 0; i < n; ++i) {
            scanf("%s", s[i]);
        }
        for (int i = 0; i < n; ++i) {
            Manacher(s[i], i);
            for (int j = 0; j < len; ++j) {
                int tmp = r[i][j] - 1;
                if (tmp <= 0) continue;
                while (tmp > 0) {
                    ++cnt[tmp];
                    tmp -= 2;
                }
            }
        }
        for (int i = 0; i <= l; ++i) {
            int sum = cnt[i];
            for (int j = 1; sum; j <<= 1) {
                int mul = min(sum, j);
                for (int p = l; p >= mul * i; --p)
                    for (int num = mul; num <= k; ++num)
                        if (num == mul || dp[num - mul][p - mul * i] > 0)
                            dp[num][p] = max(dp[num][p], 
                            dp[num - mul][p - mul * i] + mul * i);
                sum -= mul;
            }
        }
        printf("%sn", (dp[k][l] == l ? "True" : "False"));
    }
    return 0;
}

UVALive - 4260 Fortune Card Game

题意：给你n张卡片，每张卡片有三个信息——地址id、对应的字符op、下一链接地址val。而每张卡片的价值就是下一链接地址，让你构造出一个字符串。问你最大的价值。

题解：运用动态规划求最值，dp[i][j]表示第i个字符索引值为j的最大价值那么可以得到状态转移方程为：dp[i][p[j].b]=max(dp[i][p[j].b,dp[i-1][p[j].a]+p[j].b)；这个状态转移方程我一开始没看出来，看了题解并且结合题目来看之后才看懂的。

Apple Catching

题意：开始时站在树1下，第一行输入两个整数n,k，下面的n行代表在1到n秒内每次是哪棵数掉落苹果，且人在两棵树之间可以移动，但最多只能移动k次，问最多能接到几个苹果。

题解：定义dp[i][j]:前i分钟后移动j步得到的最多的苹果数，那么这到第i分钟的状态就取决于前i-1分钟移动或者不移动得到的苹果树，即dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);注意边界，还有怎么判断移动j步到哪棵树了呢，很简单，就是偶数步回到起点，奇数步到第二棵树。

#include
#include
#include
using namespace std;
#define MAX 1005
int dp[MAX][35];
int a[MAX];
int main()
{
    int n,w;
    while(~scanf("%d %d",&n,&w)){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=w;j++)
            {
                if(j>=1) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
                else dp[i][j]=dp[i-1][j];
                if(j%2+1==a[i]) dp[i][j]++;
            }
        }
        int ans=0;
        for(int i=0;i<=w;i++)
            ans=max(ans,dp[n][i]);
        printf("%dn",ans);
    }
    return 0;
}

关于本阶段的总结就写这么多，因为最近考试，导致看的题目的数量和质量受到了严重的影响，所以博客的质量也有一定程度的影响，今周就总结这么多，继续加油。