2023牛客寒假集训(小沙の抱团 hard)(动态规划)(后状态更新前状态)-爱代码爱编程
链接:https://ac.nowcoder.com/acm/contest/46813/L
来源:牛客网
小沙在玩一个抱团游戏,最开始有 nnn 个人,每次小沙有 mmm 条指令可以下达,对于第 iii 条指令可以花费 bib_ibi 的代价,要求以 xix_ixi 人为单位抱团,每个人只能在一个团里,若一个人不属于某一个恰好 xix_ixi 个人的团则将被淘汰,抱团需要所有参与抱团的人全部同意。假设参加游戏的人都足够聪明,都希望自己不被淘汰。如果你是小沙,你最少需要花费多少的代价才能使得剩余的人数最少。
每个指令都可以重复使用。
每次要求拥抱人数不能超过当前人数。例:剩余 5 人时不能要求 6个人拥抱在一起。
输入描述:
第一行输入二个整数 nnn , mmm ,代表人数以及指令个数,1≤n≤1051 \le n \le 10^{5}1≤n≤105,1≤m≤5001 \le m \le 5001≤m≤500。
随后 mmm 行,每行两个整数 bib_ibi,xix_ixi,分别代表代价以及指令的内容,1≤bi≤1051 \le b_i \le 10^51≤bi≤105,2≤xi≤1052 \le x_i \le 10^52≤xi≤105。
输出描述:
输出一个整数代表小沙最少花费的代价。
示例1
输入
复制
7 3
10 2
5 3
3 4
输出
复制
18
思路:
用人作为更新的依据,一开始用前更新后的,但时间复杂度太大了
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt=1;
queue<int>q;
struct ins{
int cost;
int cont;
}b[501];
int flag;
int a[100001],r[100001];//用于存可能达到的数
long long int dp[100001];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&b[i].cost,&b[i].cont);inst[b[i].cost]=i;
}
a[n]++;q.push(n);r[1]=n;
while(!q.empty())
{
for(int i=1;i<=m;i++)
{
int y=q.front()-q.front()%b[i].cont;
if(a[y]==0)
{
q.push(y);a[y]++;cnt++;r[cnt]=y;
}
}
// printf("%d ",q.front());
q.pop();
}
// sort(r+1,r+cnt+1,greater<int>());
for(int i=1;i<=cnt;i++)
{
flag=0;
dp[r[i]]=0x3f3f3f3f;
for(int j=1;j<=cnt;j++)
{
if(r[j]>r[i])
{
for(int v=1;v<=m;v++)
{
if(r[j]-(r[j]%b[v].cont)==r[i])
{
dp[r[i]]=min(dp[r[i]],dp[r[j]]+b[v].cost);
flag=1;
}
}
}
else
break;
}
if(flag==0)
dp[r[i]]=0;
}
long long int ans=0x3f3f3f3f;
for(int i=cnt;i>=1;i--)
{
if(r[i]!=0)
{
ans=min(ans,dp[r[i]]);
break;
}
}
printf("%lld",ans);
}
而用后更新前的,复杂度会小一些
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n,m;
struct{
ll cost;
ll cont;
}b[100001];
ll dp[100001];
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&b[i].cost,&b[i].cont);
}
for(int i=1;i<=n;i++)
{
dp[i]=0x3f3f3f3f;
}
dp[n]=0;
for(int i=n;i>=1;i--)
{
for(int j=1;j<=m;j++)
{
ll yy=i-i%b[j].cont;
dp[yy]=min(dp[yy],dp[i]+b[j].cost);
}
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(dp[i]!=0x3f3f3f3f)
{
ans=dp[i];
break;
}
}
printf("%lld",ans);
}