discuz建网站/今天的国际新闻
这周学了点数学的东西，Java的大数类，快速幂，矩阵快速幂，近几天做的codeforce不大好，思路想不出来，又陆陆续续做了几个dp背包的题，感觉dp的练习还是差的很远啊，而且dp有很大一部分是与别的知识点一块出题，遍往下学边刷题吧
luogu p2979
第一种情况不考虑大奶酪
第二种情况是考虑大奶酪；因为存在大奶酪会压扁下面的奶酪，所以T最大是T*5/4
P2979 [USACO10JAN]奶酪塔Cheese Towers - Cxs3 - 洛谷博客 (luogu.com.cn)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
const int inf=0x3f3f3f3f;
const int mod=1e9;
const int N=1e6+5;
using namespace std;
int n,t,k,v[110],h[110];
ll f[2000];
int main(){//freopen("in.txt","r",stdin);scanf("%d%d%d",&n,&t,&k);for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&h[i]);memset(f,0,sizeof(f));for(int i=1;i<=n;i++){for(int j=h[i];j<=t*5/4;j++)f[j]=max(f[j],f[j-h[i]]+v[i]);}ll ans=f[t];for(int i=1;i<=n;i++)if(h[i]>=k) ans=max(ans,f[(t-h[i])*5/4]+v[i]);cout<<ans<<endl;return 0;
}luogu p5365
一个多重背包题，懵逼的我看了题解才知道。。。钱作为容量，方案数为价值；dp[j]代表钱为j时能获得的最大方案数，容量qb就等于所有的k[i]*c[i]之和；然后就是多重背包模板了，但是我用二进制拆分的模板却不对，用普通的反而过了。。。
[洛谷]P5365 [SNOI2017]英雄联盟 (#背包dp)_A.pro的博客-CSDN博客
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<ctime>
#define ll long long
#define CHECK(x,y) (x>0&&x<=n&&y>0&&y<=m)
const int inf=0x3f3f3f3f;
const int mod=1e9;
const int N=1e6+5;
using namespace std;
ll n,m,k[1000001],c[1000001];
ll dp[1000001];
int qb;
int main(){//freopen("in.txt","r",stdin);scanf("%lld%lld",&n,&m);qb=0;for(int i=1;i<=n;i++) scanf("%lld",&k[i]);for(int i=1;i<=n;i++) scanf("%lld",&c[i]),qb+=k[i]*c[i];dp[0]=1;/*for(int i=1;i<=n;i++){int num=min(k[i],qb/c[i]);for(int k=1;num>0;k<<=1){if(k>num) k=num;num-=k;for(int j=qb;j>=c[i]*k;j--)dp[j]=max(dp[j],dp[j-c[i]*k]*k),cout<<dp[j]<<endl;;}}*/for(int i=1;i<=n;i++)for(int j=qb;j>=c[i];j--)for(int p=1;p<=k[i]&&p*c[i]<=j;p++)dp[j]=max(dp[j],dp[j-c[i]*p]*p);int ans=0;while(ans<=qb&&dp[ans]<m) ans++;cout<<ans<<endl;return 0;
}luogu p1156
dp[j]代表高度为j时最长可存活的时间，把高度d看做是容量，如果dp[j]>=d了，直接输出a[i].t即可，如果不能逃出就把垃圾能吃就吃能活多长活多长
#include<bits/stdc++.h>
using namespace std;
struct rub{int t,f,h;
}a[110];
bool cmp(rub a,rub b){return a.t<b.t;
}
int main(){//freopen("in.txt","r",stdin);int d,g;int dp[110];scanf("%d%d",&d,&g);memset(dp,0,sizeof(dp));dp[0]=10;for(int i=1;i<=g;i++)scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);sort(a+1,a+g+1,cmp);for(int i=1;i<=g;i++)for(int j=d;j>=0;j--)if(dp[j]>=a[i].t){if(j+a[i].h>=d){cout<<a[i].t<<endl;return 0;}dp[j+a[i].h]=max(dp[j+a[i].h],dp[j]);dp[j]+=a[i].f;//能吃就吃，此处修改dp[j]//的值并不影响dp[j+a[i].h]的值}cout<<dp[0]<<endl;
return 0;
}
luogu p1282
dp[i][j]代表前i个多米诺骨牌上下差为j时最小的翻转次数，去掉绝对值差值是在-5000-5000之间，数组不能为负值，所以平移一下数组，最后找出差值最小的最小翻转次数，小于等于1000就输出（因为最多能翻1000次，小于等于1000就是最小值了）
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int dp[1005][10005];
int main(){//freopen("in.txt","r",stdin);int n,a[1005],n1,n2;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&n1,&n2);a[i]=n1-n2;}int m=5000;//差最大就是5000memset(dp,inf,sizeof(dp));dp[0][m]=0;for(int i=1;i<=n;i++)for(int j=-m;j<=m;j++)//数组不能为负，所以数组平移一下dp[i][j+m]=min(dp[i-1][j+m-a[i]],dp[i-1][j+m+a[i]]+1);//前者代表不翻转，后者代表翻转int minn=inf;for(int i=0;i<=m;i++){//对可能的差遍历minn=min(dp[n][m+i],dp[n][m-i]);if(minn<=1000){cout<<minn<<endl;break;}}
return 0;
}
hdu5392
求解多个数的最小公倍数，题意就没看懂Orz，看的题解并没有快速幂，主要是如何求多个数的最小公倍数
HDU-5392-Infoplane in Tina Town_娃娃酱斯密酱的博客-CSDN博客
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3e6+10;
const ll mod=3221225473;
int t,a[N],vis[N],num[N],n;
int main(){//freopen("in.txt","r",stdin);cin>>t;while(t--){scanf ("%d", &n);for (int i = 1; i <= n; i++){scanf ("%d", &a[i]);vis[i] = 0;num[i] = 0;}for(int i=1;i<=n;i++){if(!vis[i]){int cnt=0;int k=i;while(!vis[k]){//求循环长度vis[k]=1;cnt++;k=a[k];}for(int j=2;j*j<=cnt;j++){int top=0;if(!(cnt%j)){//求质因数while(!(cnt%j)){cnt/=j;top++;}}num[j]=max(num[j],top);//维护最高次幂的质因数}if(cnt>1){num[cnt]=max(num[cnt],1);}}}ll res = 1;for (int i = 2; i <= n; i++){while (num[i]--){res = res * i % mod;}}cout << res << endl;}
return 0;
}
luogu p2224
dp[j]表示A机器用时j，B机器的用时，挨个判断每个任务用哪种情况更好
(1条消息) 洛谷 P2224 [HNOI2001]产品加工 解题报告_weixin_30940783的博客-CSDN博客
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#define ll long long
const int inf=0x3f3f3f3f;
using namespace std;
int main(){//freopen("in.txt","r",stdin);int n,c[4],dp[30005],r=0;scanf("%d",&n);memset(dp,inf,sizeof(inf));dp[0]=0;for(int i=1;i<=n;i++){scanf("%d%d%d",&c[0],&c[1],&c[2]);r+=max(c[0],max(c[1],c[2]));for(int j=r;j>=0;j--){if(c[1])//这个任务用b机器做dp[j]+=c[1];else dp[j]=inf;if(j>=c[0])//这个任务用a机器做dp[j]=min(dp[j],dp[j-c[0]]);if(j>=c[2])//这个任务a和b一起做dp[j]=min(dp[j],dp[j-c[2]]+c[2]);}}int ans=inf;for(int i=0;i<=r;i++)ans=min(ans,max(dp[i],i));//选A和B用时最长的，因为两台机器都做完才算做完cout<<ans<<endl;
return 0;
}
codeforce B Update Files
思路好像是对的，但是老是想不出那个代码的算式要怎么写，还是代码能力太差了，如果没有k限制的话，copy数是2的n次方递增的，所以看看mul一直乘以2小于k的次数cnt，然后n再减去mul，剩余的除以k再加上cnt就是答案，还有就是不要忘了取余
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#define ll long long
const int inf=0x3f3f3f3f;
using namespace std;
int main(){//freopen("in.txt","r",stdin);ll t,n,k;scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&k);ll cnt=0,mul=1;while(mul<k){cnt++;mul*=2;}if(mul<n)cnt+=(n-mul)/k+(((n-mul)%k)!=0);printf("%lld\n",cnt);}
return 0;
}