25.3.9刷题

P3375 【模板】KMP

https://www.luogu.com.cn/problem/P3375

题解

kmp算法模板，输出匹配开始位置，最后再输出next数组

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

const int N=1000010;
string s,p;
int ne[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    s=" ",p=" ";
    string s1,p1;
    cin>>s1>>p1;
    s+=s1,p+=p1;
    int lens=s.length()-1;
    int lenp=p.length()-1;
    
    for(int i=2,j=0;i<=lenp;i++)
        {
            while(j&&p[i]!=p[j+1]) j=ne[j];
            if(p[j+1]==p[i]) j++;
            ne[i]=j;
        }

    for(int i=1,j=0;i<=lens;i++)
        {
            while(j&&s[i]!=p[j+1]) j=ne[j];
            if(s[i]==p[j+1]) j++;
            if(j==lenp)
            {
                cout<<i-lenp+1<<'\n';
                j=ne[j];
            }
        }
    for(int i=1;i<=lenp;i++) cout<<ne[i]<<' ';
    return 0;
}

P1507 NASA的食物计划

https://www.luogu.com.cn/problem/P1507

题解

01背包的变形，限制条件变成了两个：体积、质量。

只需开个二维dp[i][j]数组，第一个下标代表体积，第二个下标代表质量。表示体积最大为i的情况下，重量最大为j时的最大价值

状态转移方程：dp[j][l] = max(dp[j][l], dp[j - h1[i]][l - t1[i]] + k[i])

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

const int N = 405,M=51;
int h, t;
int n;
int h1[M], t1[M], k[M];
int dp[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> h >> t;
	cin >> n;
	for (int i = 1; i <= n; i++)//遍历每个物品，选还是不选
	{
		cin >> h1[i] >> t1[i] >> k[i];
		for (int j = h; j >= h1[i]; j--)//倒序遍历体积，防止重复
		{
			for (int l = t; l >= t1[i]; l--)//倒序遍历质量，防止重复
			{
				dp[j][l] = max(dp[j][l], dp[j - h1[i]][l - t1[i]] + k[i]);
			}
		}
	}
	cout << dp[h][t];

	return 0;
}

P1470 最长前缀 Longest Prefix

https://www.luogu.com.cn/problem/P1470

题解

dp问题。dp[i]表示从1到i的前缀字符串是否可以用p拼接.

状态转移：if(h.count(t)&&dp[i-j]) dp[i]=true; 如果从1到i-j可以表示，且i-j到i在p中存在，那么dp[i]也可以表示

#include<bits/stdc++.h>

using namespace std;

const  int N = 200010;
int max1 = 0;
string s, x;
unordered_set<string> h;
int dp[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	while (cin >> s, s != ".")//读取输入
	{
		h.insert(s);
		max1 = max(max1, (int)s.size());//存最大长度
	}
	s = " ";//先初始一个字符，便于从1开始遍历
	while (cin >> x) s += x;//读取字符串，可以有多行
	dp[0] = true;//初始dp[0]合法
	int ans = 0;
	for (int i = 1; i < s.size(); i++)//遍历字符串
	{
		for (int j = min(max1, i); j >= 1; j--)
		{
			string t = s.substr(i - j + 1, j);
			if (h.count(t) && dp[i - j])
			{
				dp[i] = true;
				ans = i;
				break;
			}
		}
	}
	cout << ans;

	return 0;
}