目前进度——动态规划1：线性dp、背包问题，区间
好题
1003 可爱の星空
标签
递推 分治
思路
- 记 \(dp_i\) 表示将 \(i\) 颗点合并为一个连通块所需的最小代价。根据贪心思想：若目前的总点数 \(n\) 为偶数，则 \(dp_n=2*dp_{\frac{n}{2}}\)；若目前的总点数 \(n\) 为奇数，则 \(dp_n=dp_{[\frac{n}{2}]+1}+dp_{[\frac{n}{2}]}+1\)。故递推即可。
- 时间复杂度为 \(\mathcal O(t\log n)\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll n;
map<ll,ll> mp;
void dp(ll x)
{
if(mp.find(x)!=mp.end())
return;
if(x==1||x==0)
{
mp[x]=0;
return;
}
if(x&1)
{
dp(x>>1),dp((x>>1)+1);
mp[x]=mp[x>>1]+mp[(x>>1)+1]+1;
}
else dp(x>>1),mp[x]=mp[x>>1]*2;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
dp(n);
printf("%lld\n",mp[n]);
}
return 0;
}
1005 花店橱窗
标签
递推
思路
- 有条件的线性递推，时间复杂度为 \(\mathcal O(FV^2)\)。
- 易错点在于初始化：
if(i==f&&j>=f) dp[i][j]=vi[i][j];；
错误的写为if(i==f) dp[i][j]=vi[i][j]会导致错误。由此得到收获，初始化一定要严谨。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
const long long INF=-9223372036854775808;
int f,v,fa[maxn][maxn];
long long vi[maxn][maxn],dp[maxn][maxn];
int main()
{
scanf("%d%d",&f,&v);
for(int i=1;i<=f;i++)
{
for(int j=1;j<=v;j++)
{
dp[i][j]=INF,fa[i][j]=j;
scanf("%lld",&vi[i][j]);
if(i==f&&j>=f) dp[i][j]=vi[i][j];
}
}
for(int i=f-1;i>=1;i--)
{
for(int j=1;j<=v-(f-i);j++)
{
for(int k=j+1;k<=v;k++)
{
if(dp[i+1][k]!=INF && vi[i][j]+dp[i+1][k]>dp[i][j])
{
dp[i][j]=dp[i+1][k]+vi[i][j],fa[i][j]=k;
}
}
}
}
long long maxid=1,maxdp=dp[1][1];
for(int i=2;i<=v;i++)
{
if(dp[1][i]>maxdp)
{
maxid=i,maxdp=dp[1][i];
}
}
printf("%lld\n",maxdp);
for(int i=1,j=maxid;i<=f;i++)
{
printf("%d ",j);
j=fa[i][j];
}
return 0;
}
1007 钉子和小球 PS:好题
标签
概率DP
思路
- 概率DP，本题易得到 \(\mathcal O(n^2)\) 的做法。
- 注意点：由无钉子处向其他点的转移与由有钉子处向其他点的转移是不同的，具体表现在权重不同。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=55;
int n,m;
ll dp[maxn][maxn];
char tp[maxn][maxn];
ll gcd(ll a,ll b)
{
if (a<b) swap(a,b);
if(b==0) return a;
else return gcd(b,a%b);
}
int main()
{
scanf("%d%d",&n,&m);
char ch=getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
while(ch=='\n'||ch==' ')
ch=getchar();
tp[i][j]=ch;
ch=getchar();
}
}
dp[1][1]=1;
for(int i=0;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(tp[i][j]=='*')
dp[i+1][j]+=dp[i][j],dp[i+1][j+1]+=dp[i][j];
else
{
if(i+2<=n+1) dp[i+2][j+1]+=4*dp[i][j];
else if(i+2==n+2) dp[n+1][j+1]+=2*dp[i][j];
}
}
}
ll sum=0;
for(int i=1;i<=n+1;i++)
sum+=dp[n+1][i];
while(sum%2==0&&dp[n+1][m+1]%2==0) sum/=2,dp[n+1][m+1]/=2;
printf("%lld/%lld",dp[n+1][m+1],sum);
return 0;
}