布告张贴
分析
背包变式
- 初始化，属性是最小值所以初始化最大值
- 边界，长度为0所需布匹为0
- 转移，除了由 $n-a[i]->n$ ，还应该考虑 $i->i+a[i]-1$ ，即除了长度覆盖还有位置也需要对应。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5005,INF=0x3f3f3f3f;
int t,n,dp[N],a[N];
//dp[i] 表示长i至少布告数量
//[i,ai+i-1]这个是单独一块的长度
void solve()
{
cin>>n;
memset(dp,0x3f,sizeof dp);
//因为求最小值，所以初始化要最大，动脑子
for(int i=1;i<=n;i++)cin>>a[i];
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=min(n,a[i]+i-1);j>=max(a[i],i);j--)
{
dp[j]=min(dp[j-a[i]]+1,dp[j]);
}
}
if(dp[n]>INF/2)cout<<-1<<endl;//还是一半的判断好用
else cout<<dp[n]<<endl;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}
组比赛
分析
背包变式
最关键的还得是想好状态表示和转移，这题具体看代码吧。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rtp(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5005;
int n,m,t,a[105][105];
bool dp[105][5005];
//dp[i][j]，到第i场比赛的j分数是否存在
void solve()
{
cin>>n>>m;
rep(i,1,n)rep(j,1,m)cin>>a[i][j];
cin>>t;
//边界
dp[0][0]=true;
rep(i,1,n)
rep(j,1,m)
rep(k,a[i][j],5000)
dp[i][k]=dp[i][k]||dp[i-1][k-a[i][j]];
int z=1e9;
rep(i,1,5000)
if(dp[n][i])z=min(abs(i-t),z);
cout<<z;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// cin>>t;
int t=1;
while(t--)solve();
return 0;
}
线段
分析
关键是有了思路就好写了，思路——状态表示，明显是可以往左端点和右端点进行两类 $dp$
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=3e4+10;
int n,a[N][2],dp[N][2];
//取绝对值，这样避免分类讨论，还有其实可以开两个数组的，这样更直观
//模拟全wa，因为要考虑的点有点多
int d(int x,int y)
{
return abs(x-y);
}
void solve()
{
cin>>n;
//0左1右
for(int i=1;i<=n;i++)cin>>a[i][0]>>a[i][1];
dp[1][1]=d(1,a[1][1]);
dp[1][0]=d(1,a[1][1])+d(a[1][1],a[1][0]);
for(int i=2;i<=n;i++)
{
dp[i][0]=min(dp[i-1][0]+d(a[i-1][0],a[i][1])+d(a[i][1],a[i][0]),dp[i-1][1]+d(a[i-1][1],a[i][1])+d(a[i][1],a[i][0]))+1;
dp[i][1]=min(dp[i-1][1]+d(a[i-1][1],a[i][0])+d(a[i][1],a[i][0]),dp[i-1][0]+d(a[i-1][0],a[i][0])+d(a[i][0],a[i][1]))+1;
}
cout<<min(dp[n][0]+d(a[n][0],n),dp[n][1]+d(a[n][1],n));
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
while(t--)solve();
return 0;
}
牛的展览
分析
背包变式
坑点：
- 智商情商有正有负，$dp$ 数组要偏移，数组偏移后初始化，枚举也都是要偏移相同的量的
- 既然是背包，那就要选出谁为价值谁为体积，也就是为体积的一方是定下来的，是要枚举的
- 对于负的值要处理，是正序枚举
- 若结果一直不对，那么可能是 $dp$ 数组开小了，越界了
- 这题暴搜可以偏一些分
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int n,a[N],b[N];
int st[N];
int dfs(int u,int s1,int s2)
{
int ans1=0,ans2=0;
if(u>n)
{
if(s1<0||s2<0)return 0;
return s1+s2;
}
ans1=dfs(u+1,s1,s2);
ans2=dfs(u+1,s1+a[u],s2+b[u]);
int ans=max(ans1,ans2);
return ans;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
cout<<dfs(1,0,0)<<endl;
return 0;
}
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=400000,M=800000,INF=0x3f3f3f3f;//这些数据要会算
int n,a[N],b[N],dp[M+5];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
//边界
memset(dp,-0x3f,sizeof dp);
dp[N]=0; //注意偏移了
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
for(int i=1;i<=n;i++)
{
if(a[i]<=0&&b[i]<=0)continue;
if(a[i]>=0)
for(int j=M;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
else
for(int j=0;j<=M+a[i];j++)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
int ans=-INF;
for(int i=N;i<=M;i++)//枚举智商
{
if(dp[i]>=0)ans=max(ans,i+dp[i]-N);
}
cout<<ans;
return 0;
}
久别重逢
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,M=1e9+7;
int n,k,dp[N]={1};
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
if(i>=k)
dp[i]=(dp[i-1]+dp[i-k])%M;
int ans=0;
for(int i=0;i<=n;i++)ans+=dp[i];
cout<<ans%M;
//这里取模很可能不对，所以最好还是每步加的时候取模
return 0;
}
