FuoFuo之小碎念剧场
搞了四个多钟的matlab，终终终于有了一丢丢的结果，起码能够将人的五官分成不同的图片了，现在还差数据集和接口，为什么我的头发又长了呢？//当我没说。
昨天，哦不，前天，见到了教主，师兄说的时候我是真的一点都不相信，那个每次查题解冷不丁会在百度上出现的教主居然就在眼前，激动的一批，虽然自己真的很菜很菜，但是还是很想成为一个真正的acmer，也许会很耗时很耗脑，不过我是真的挺喜欢的~
想起前天一个笑话
“同学，对于今天比赛，你有什么想吐槽的吗？”
“今天中午的薯条是不是没放盐？！”
真没想到还能有麦当劳，起码比蓝桥杯舒服的多。
在南海没什么资源，想学算法只能靠自己，我很庆幸自己能够遇到很多很多优秀的师兄师姐，从而让我更加坚定自己想要成为一个acmer的想法
不管怎么样，事会多，人会累，有时候需要舍弃很多很多的东西，每天一个人上课，一个人吃饭，一个人泡图书馆，因为没有氛围，所以只能自己营造。
好啦，瞎逼逼结束！
总结完早点睡觉，明天看看交了钱代拿的快递能不能送到宿舍//估计是不行了，已不抱有希望~

01背包

状态转移方程 (这是倒着来的)

dp[n][j]=0
if(j<w[i])
    dp[i][j]=dp[i+1][j];
else
    dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);

01背包

dp[i+1][j]从前i个物品中选出总重量不超过j的物品时总价值的最大值

逆向

#include <bits/stdc++.h>
using namespace std;
    int n,dp[100][100],W,v[100],w[100];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    cin>>W;
    for(int i=n-1;i>=0;i--)
        for(int j=0;j<=W;j++){
            if(j<w[i])
                dp[i][j]=dp[i+1][j];
            else
            {
                dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
            }
        }
    cout<<dp[0][W];
    return 0;
}

正向

#include <bits/stdc++.h>
using namespace std;
    int n,dp[100][100],W,v[100],w[100];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    cin>>W;
    for(int i=0;i<n;i++)
        for(int j=0;j<=W;j++){
            if(j<w[i])
                dp[i+1][j]=dp[i][j];
            else
            {
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    cout<<dp[n][W];
    return 0;
}

 

01背包水题

Bone Collector

饭卡

 //#include <bits/stdc++.h>
using namespace std;

int v[1001],n,m,dp[1001];
int main(){
    while(cin>>n&&n!=0){
        for(int i=0;i<n;i++)
            cin>>v[i];
        cin>>m;
        if(m<5){
            cout<<m<<endl;
          continue; 
        }
        sort(v,v+n);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n-1;i++)
            for(int j=m-5;j>=v[i];j--)
                dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
        cout<<m-dp[m-5]-v[n-1]<<endl;
    } 
    return 0;
} 

 
 

LCS

定义

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

区别

（1）字符子串：指的是字符串中连续的n个字符，如abcdefg中，ab，cde，fg等都属于它的字串。
（2）字符子序列：指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改
变其前后顺序。如abcdefg中，acdg，bdf属于它的子序列，而bac，dbfg则不是，因为它们与字符串的字符顺序不一致。
（3） 公共子序列：如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。如对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说，序列1,8,7是它们的一个公共子序列。

Title

Explain

dp[i][j]:=s1...si和t1...tj对应的LCS长度,由此，s1...si和t1...tj对应的公共子列可能是
当si+1=tj+1时，在
s1...si和t1...tj的公共子列末尾追加上si+1
s1...si和t1...tj+1的公共子列
s1...si+1和t1...tj的公共子列
三者中的某一个，所以就有如下的递推关系成立

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1001],t[1001];
int dp[1001][1001];
int main(){
    int n,m;
    cin>>n>>m;
    scanf("%s%s",s,t);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(s[i]==t[j])
                dp[i+1][j+1]=dp[i][j]+1;
            else
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
        }
    cout<<dp[n][m]<<endl;
    return 0;   
}

2019.5.14凌晨
*****************************************************今天先写到这啦，去解决100道文学题**********************************************************

Common Subsequence

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>       //这里是memset的头文件
#include <cstdlib> 
#include <algorithm>
using namespace std;
typedef long long ll;
char s[1001],t[1001];
int dp[1001][1001];
int main(){
    while(scanf("%s%s",s,t)!=EOF){
        memset(dp,0,sizeof(dp));
        int n=strlen(s),m=strlen(t);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                if(s[i]==t[j])
                    dp[i+1][j+1]=dp[i][j]+1;
                else
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            } 
        cout<<dp[n][m]<<endl;
    }

    return 0;   
}

 

1006 最长公共子序列Lcs

这是一道有bug的题
此题的切入点就是动态规划，通过动归来确定哪些字符是最长公共子序列中的字符

//#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1001],t[1001],a[1001];
int dp[1001][1001];
int p;

void output(int x,int y){
    while(x>0&&y>0){
        if(s[x]==t[y]){
            a[p++]=s[x];
            x--,y--;
        }else if(dp[x][y-1]<=dp[x-1][y]){        //这里其实这么输入结果是不对的，但是最后却AC了，神奇，但是思路是没有错的！
        //说明之前的最长lcs是在s[0,y-1]和t[0,x]中!
            x--;
        }else{
            y--;
        }
    }
}

//要确保dp和st都是从1开始的，好计算； 

int main(){
    while(scanf("%s%s",s,t)!=EOF){
        p=0;
        memset(dp,0,sizeof(dp));
        int n=strlen(s),m=strlen(t);
        for(int i=n-1;i>=0;i--) s[i+1]=s[i];
        for(int i=m-1;i>=0;i--) t[i+1]=t[i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(s[i]==t[j])
                    {
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            } 
        output(n,m);
        for(int i=strlen(a)-1;i>=0;i--)
            cout<<a[i];
        cout<<endl;
    }

    return 0;   
}

 

Advanced Fruits

在LCS的基础之上加上路径记录，生成dp数组的时候做上标记，之后按顺序输出结果字符串。注意还要考虑一下没有公共子序列的情况。

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring> 
#include <cstdlib> 
#include <algorithm>
using namespace std;
typedef long long ll;
char s[1001],t[1001],a[1001];
int dp[1001][1001];
int p;

void output(){
    int i=strlen(s),j=strlen(t);
    while(dp[i][j]){
        if(s[i-1]==t[j-1]){
            a[p++]=s[--i];
            j--;
        }else if(dp[i][j-1]<dp[i-1][j]){
            a[p++]=s[--i];
        }else if(dp[i-1][j]<=dp[i][j-1]){
            a[p++]=t[--j];
        }
    }
    while(i!=0)
        a[p++]=s[--i];
    while(j!=0)
        a[p++]=t[--j];
    for(int i=p-1;i>=0;i--){
        printf("%c",a[i]);
    }
    printf("\n");
}

//要确保dp和st都是从1开始的，好计算； 

int main(){
    while(scanf("%s%s",s,t)!=EOF){
        p=0;
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        int n=strlen(s),m=strlen(t);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                if(s[i]==t[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        output();
    }
    return 0;   
}

5.15FuoFuo小剧场之二
数基好难，现在才知道高数离散线代是多么和蔼