当前位置：首页 > news >正文

苏州专业做网站的公司哪家好/seo投放是什么意思

news 2025/6/29 23:12:51

苏州专业做网站的公司哪家好,seo投放是什么意思,wordpress 文章副标题,手机网站搜索链接： https://www.luogu.com.cn/problem/P1021 现在的状态就是找到一个提高题来做，做了半天，被迫看题解。一道题从读题，想思路，看题解，真正明白，写代码。前前后后差不多两三个小时就过去了&am…

链接：
https://www.luogu.com.cn/problem/P1021

现在的状态就是找到一个提高题来做，做了半天，被迫看题解。一道题从读题，想思路，看题解，真正明白，写代码。前前后后差不多两三个小时就过去了（果然蒟蒻的本质始终没变~ - ~）

就来看这个题吧：

题意：

给你两个数n和k，k代表自定义k个不同的数，n代表从k中取n个数（可重复），最后由这n个数可以组成连续的从1到max的数，输出max的最大值和最大值对应的K和不同的数的值。

思路：

因为只是看懂了别人的思路就开始写这篇博客了，主要的是怕在写代码的时候万一由出现代码不过关，调试几个小时的情况导致没心情写思路。

思路是这样的，我们首先要知道，如果要完成从1开始到某个数连续的话，这k个数是有一定的范围的。

就拿n=3，k=3为例来说吧。
首先k的第一个数肯定是1（不用质疑）
k的第二个数，他的最小是就是2，他的最大值的话，因为n=3，全部由1来构成的话最多是3。所以第二个数最大是4。
以此类推：f[1]=1; f[i]=(f[i-1]+1,f[i-1] * n+1);
我们知道了每一个数的范围就可以用暴力搜索的方法。

在这里插入图片描述

像是这样，在n=3,k=3的条件下，从1,2,3开始搜索，直到搜索到1,4,7.从中找出能够使连续达到最大的那一组数输出。

对每一组符合条件的数来进行查找看看他们能够遍历的最大数是多少。

现在就剩下一个问题了，就是怎么找到每组数中能够达到的最大连续数了。

这个大问题最后就简化成一个给定一组固定的数让你求他能够组成的最大连续数的问题了。一看最大最小，就应该会想到dp了。那么怎么求呢？
因为是连续的我们可以从1开始，然后看这组数能不能在n个数之内组成。
那么dp数组代表的意思就是：dp[i]代表第i个数能用给定的数中最少几个数来表示。
dp方程：dp[i]=min(dp[i],dp[i-f[j]]+1);

这一部分的代码就是

while(dp[i]<=n){i++;dp[i]=INF;for(int j=1;j<=k&&i-f[j]>=0;j++){dp[i]=min(dp[i],dp[i-f[j]]+1);}}

那么这个题目也结束了。现在去肝代码去了。（不出意外很快就回来了）

代码：
还算比较的顺利

#include <bits/stdc++.h>
#include<iostream>
using namespace std;int read(){int f=1,x=0;char ss=getchar();while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}return f*x;}
int n,m,sum=0;//sum代表找最大的连续数
int f[20],dp[5000],arr[20];//f[i]遍历需要查找的数组。arr找最大的那一组数（输出的）
void dfs(int x){
if(x==m+1)
{memset(dp,0,sizeof dp);int i=0;while(dp[i]<=n){i++;dp[i]=1000000000;for(int j=1;j<=m&&f[j]<=i;j++)dp[i]=min(dp[i],dp[i-f[j]]+1);if(i-1>sum){for(int j=1;j<=m;j++)arr[j]=f[j];sum=i-1;}}return ;
}
for(int i=f[x-1]+1;i<=f[x-1]*n+1;i++)
{f[x]=i;dfs(x+1);
}}int main(){std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>m;f[1]=1;dfs(2);
for(int i=1;i<=m;i++)cout<<arr[i]<<" ";
cout<<endl;
cout<<"MAX="<<sum<<endl;
}