25.3.8刷题

P1203 坏掉的项链

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

题解

用暴力搜素。关于字符串的操作：substr、erase、reverse

字符串是个环，处理方法：再复制一份

#include<bits/stdc++.h>
using namespace std;
string s,s1,s2;
int ans,ans1;
int n;

void search(int a)
{
    s1=s.substr(a);//取a之后的子串
    s1+=s;//再复制，相当于环
    s1.erase(n);//删除n之后的字符
    s2=s1;//再复制一个给s2
    reverse(s2.begin(),s2.end());//s2反转，相当于倒着遍历
    int j=0;
    while(s1[j]=='w')//第一个不是w的字符
        {
            ans++;
            j++;
        }
    for(int i=j;i<n;i++)//遍历
    {
        if(s1[i]==s1[j]||s1[i]=='w')
        {
            ans++;
        }
        else break;
    }
    j=0;
    while(s2[j]=='w') ans++,j++;//另一方向，第一个不是w的字符
    for(int i=j;i<n;i++)//遍历
        {
            if(s2[i]==s2[j]||s2[i]=='w') ans++;
            else break;
        }
    ans1=max(ans1,ans);//记录当前最大的结果
    ans=0;//每次结束要把ans清零
}

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

    cin>>n>>s;
    for(int i=0;i<n;i++) search(i);
    ans=min(ans1,n);//不能超过字符总长度
    cout<<ans;
    
    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;
}