尽力而为，因为最近大作业太多了，实在没时间写代码了。左侧目录有的就是文章里有的
A – [IOI1994]数字三角形 Number Triangles
真·入门题
#include<bits/stdc++.h>
using namespace std;
long long dp[1005][1005],ai[1005][1005];
long long n,ans;
int main(){
cin>>n;ans=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>dp[i][j];
dp[i][j] += max(dp[i-1][j],dp[i-1][j-1]);
}
}
for(int i=1;i<=n;i++){
ans = max(ans,dp[n][i]);
}
cout<<ans<<endl;
}B – Sumsets
做完才反应过来可以用完全背包……用了找规律的方法，发现了迭代式：
$$
f(x) =
\begin{cases}
f(x-1) &,2 \nmid x \
f(x-1) + f(\frac{x}{2}) &,2 \mid x
\end{cases}
$$
#include<iostream>
#include<cstring>
using namespace std;
/************************\
* n = 1 : 1
* n = 2 : 2
* n = 3 : 2
* n = 4 : 4
* n = 5 : 4
* n = 6 : 6
* n = 7 : 6
* n = 8 : 10
* n = 10 : 14
* 1 1 1 1 1 1 1 1 1 1
* 1 1 1 1 1 1 1 1 2
* 1 1 1 1 1 1 2 2
* 1 1 1 1 2 2 2
* 1 1 2 2 2 2
* 2 2 2 2 2
* 1 1 1 1 1 1 4
* 1 1 1 1 2 4
* 1 1 2 2 4
* 2 2 2 4
* 1 1 4 4
* 2 4 4
* 1 1 8
* 2 8
* 《完 全 背 包 是 什 么》
\************************/
long long dp[1000005];
int n;long long pow2[32];
const long long MOD = 1e9;
/*long long f(long long cur){
//cout<<cur<<endl;
if(dp[cur]!=-1)return dp[cur];
return dp[cur]=((cur%2)?f(cur-1):f(cur/2)+f(cur-1)) % MOD;
}*/
int main(){
cin>>n;pow2[0] = 1;
for(int i=1;i<=31;i++){
pow2[i] = pow2[i-1] * 2;
}
memset(dp,-1,sizeof(dp));
dp[1] = 1;
for(long long i=2;i<=n;i++){
if(i%2){
dp[i] = dp[i-1];
}else{
dp[i] = dp[i-1] + dp[i/2];
}
dp[i] %= MOD;
}
cout<<dp[n]<<endl;
return 0;
}C – 开心的金明
简单的01背包。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[30005],n,m,vi[30005],wi[30005],ans;
int main(){
freopen("happy.in","r",stdin);
freopen("happy.out","w",stdout);
memset(dp,-1,sizeof(dp));
cin>>n>>m;dp[0] = 0;
for(int i=1;i<=m;i++){
cin>>vi[i]>>wi[i];
wi[i] *= vi[i];
for(int j=n;j>=vi[i];j--){
if(dp[j-vi[i]]!=-1){
dp[j] = max(dp[j],dp[j-vi[i]]+wi[i]);
}
}
}
ans = 0;
for(int j=n;j>=0;j--){
if(dp[j]!=-1){
ans = max(dp[j],ans);
}
}
cout<<ans<<endl;
return 0;
}D – Piggy-Bank
优化没写对，弄巧成拙了。不需要优化应该也能过。
/********************
* 目测像是完全背包
* 但是希望值尽可能小
* 单调优化：如果价格不小于A.v，质量不大于A.w，直接丢掉
*/
namespace lovelive{
typedef long long LL;
struct P{
LL v,w;
friend bool operator <(const P a,const P b){
//尽可能找到重量更大且面值更小的
return a.w == b.w ? a.v > b.v : a.w < b.w ;
}
};
priority_queue<P> q;
int n,_t;P cur;
LL e,f,m,maxv=50005;
LL dp[10005];
void main(){
cin>>e>>f>>n;
m = f - e;maxv = 50005;
for(int i=1;i<=n;i++){
cin>>e>>f;
q.push(P{e,f});
}
memset(dp,-1,sizeof(dp));
dp[0] = 0;
while(!q.empty()){
cur = q.top();q.pop();
//if(cur.v>maxv)continue;
maxv = cur.v;
for(int i=0;i<=m-cur.w;i++){
if(dp[i]!=-1){
if(dp[i+cur.w]==-1){
dp[i+cur.w] = dp[i] + cur.v;
}else{
dp[i+cur.w] = min(dp[i+cur.w],dp[i] + cur.v);
}
}
}
}
if(dp[m]==-1){
cout<<"This is impossible."<<endl;
}else{
cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl;
}
}
}E – Buying Hay 购买干草
完全背包。注意可以浪费。
namespace lovelive{
LL dp[60000],pi,ci,n,h,maxpi,ans;
void main(){
cin>>n>>h;maxpi = 0;
memset(dp,-1,sizeof(dp));
dp[0] = 0;
for(int i=1;i<=n;i++){
cin>>pi>>ci;
maxpi = max(maxpi,pi);
for(LL j=0;j<=h;j++){
if(dp[j]!=-1){
if(dp[j+pi]==-1){
dp[j+pi] = dp[j] + ci;
}else{
dp[j+pi] = min(dp[j+pi],dp[j] + ci);
}
}
}
}
ans = -1;
for(LL i=h;i<h+maxpi;i++){
if(dp[i]!=-1)ans = (ans==-1?dp[i]:min(ans,dp[i]));
}
cout<<ans<<endl;
return;
}
}F – Dividing
做了一点小优化（二进制分组优化）的多重背包。优化见OI-wiki。
namespace lovelive{
LL ai[7],pow2[61],tot,cnt,ncnt,nicos[20005];
bool flag,dp[120005];
void init(){
cnt = 0;
pow2[0] = 1;
for(int i=1;i<=60;i++){
pow2[i] = pow2[i-1]<<1;
}
}
void end(bool ok){
cout<<"Collection #"<<cnt<<":"<<endl<<"Can";
if(!ok){
cout<<"'t";
}
cout<<" be divided."<<endl<<endl;
}
bool main(){
tot = 0;cnt ++;ncnt = 0;
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(int i=1;i<=6;i++){
cin>>ai[i];tot += ai[i] * i;
for(int j=0;ai[i]>=pow2[j];j++){
nicos[++ncnt] = (pow2[j]*i);
ai[i] -= pow2[j];
}
if(ai[i])nicos[++ncnt] = (ai[i]*i);
}
if(!tot)return false;
if(tot % 2){
end(false);
return true;
}
tot /= 2;
for(int i=1;i<=ncnt;i++){
//cout<<nicos[i]<<endl;
for(int j=tot;j>=nicos[i];j--){
if(dp[j-nicos[i]]){
dp[j] = true;
//cout<<j-nicos[i]<<" -> "<<j<<endl;
}
}
}
end(dp[tot]);
return true;
}
}G – Coins
跟上一题差不多。
namespace lovelive{
LL pow2[61];
LL n,m,ai[105],ci[105];
LL nicos[100005],cnt,ans;
bool dp[100005];
void init(){
pow2[0] = 1;
for(int i=1;i<=60;i++){
pow2[i] = pow2[i-1]<<1;
}
}
bool main(){
cnt = 0;ans = 0;
cin>>n>>m;
memset(dp,0,sizeof(dp));
dp[0] = 1;
if(n==0&&m==0)return false;
for(int i=1;i<=n;i++){
cin>>ai[i];
}
for(int i=1;i<=n;i++){
cin>>ci[i];
for(int j=0;ci[i]>=pow2[j];j++){
nicos[++cnt] = ai[i] * pow2[j];
ci[i] -= pow2[j];
}
if(ci)nicos[++cnt] = ai[i] * ci[i];
}
for(int i=1;i<=cnt;i++){
for(int j=m;j>=nicos[i];j--){
if(dp[j-nicos[i]])dp[j] = true;
}
}
for(int i=1;i<=m;i++){
ans += dp[i];
}
cout<<ans<<endl;
return true;
}
}I – FatMouse’s Speed
在做之前先按照其中一个权值排个序，然后再按照另一个权值做最长严格单调子序列。
namespace lovelive{
typedef pair<pair<LL,LL>,LL> P;
LL n,wi,si,dp[1005],last[1005],ansi[1005];
P nicos[1005];
bool cmp(const P a,const P b){
return a.first.first == b.first.first ?
a.first.second > b.first.second :
a.first.first < b.first.first;
}
void main(){
n = 0;
memset(dp,0,sizeof(dp));
memset(last,0,sizeof(last));
while(cin>>wi>>si)n++,nicos[n] = {{wi,si},n};
sort(nicos+1,nicos+n+1,cmp);
for(int i=1;i<=n;i++){
//cout<<"\t"<<nicos[i].first.first<<"\t"<<nicos[i].first.second<<endl;
for(int j=1;j<i;j++){
if(nicos[j].first.first<nicos[i].first.first &&
nicos[j].first.second>nicos[i].first.second){
if(dp[i]<dp[j]+1){
dp[i] = dp[j] + 1;
last[i] = j;
}
}
}
}
wi = n;si = 0;
for(int i=n;i>=1;i--){
if(dp[i]>dp[wi])wi = i;
}
while(wi){
ansi[++si] = wi;
wi=last[wi];
}
cout<<si<<endl;
for(int i=si;i>=1;i--){
cout<<nicos[ansi[i]].second<<endl;
}
return;
}
}K – 石子归并 V2
namespace lovelive{
const LL INF = 114514191981000;
LL dp[2005][2005],m[2005][2005],n,ans,ai,bi,sumi[2005];
LL calc(LL l,LL r){
if(r<l){
return sumi[n-1] + sumi[r] - (l==0?0:sumi[l-1]);
}else{
return sumi[r] - (l==0?0:sumi[l-1]);
}
}
void main(){
cin>>n;
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
cin>>sumi[i];
if(i)sumi[i]+=sumi[i-1];
m[i][i] = i;
}
for(int i=n;i<n*2;i++){
sumi[i] = sumi[i-n] + sumi[n-1];
m[i][i] = i;
}
for(int k=2;k<=n;k++){
for(int l=0,r=k-1;l<n;l++,r++){
//四！边！形！不！等！式！
dp[l][r] = INF;
for(int k=m[l][r-1];k<=m[l+1][r];k++){
if(dp[l][k] + dp[k+1][r] + calc(l, r) < dp[l][r]){
dp[l][r] = dp[l][k] + dp[k+1][r] + calc(l, r);
m[l][r] = k;
}
}
//cout<<l<<" "<<r<<" "<<dp[l][r]<<" "<<m[l][r]<<endl;;
dp[(l+n)%(2*n)][(r+n)%(2*n)] = dp[l][r];
m[(l+n)%(2*n)][(r+n)%(2*n)] = m[l][r]+n;
}
}
ans = dp[0][n-1];
for(int i=1;i<n;i++){
ans = min(ans,dp[i][i+n-1]);
}
cout<<ans<<endl;
return;
}
}L – Multiplication Puzzle
朴实无华的区间DP。
namespace lovelive{
const LL INF = 114514191981000;
LL n,ai[105],dp[105][105];
void main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>ai[i];
}
memset(dp,0,sizeof(dp));
/*************************\
* 如何dp？
* dp[i][j] 代表对 [i,j]区间内进行活动
* [i] (i+1,k-1) [k] (k+1,j-1) [j]
* dp[i][j] = min(dp[i][k] + dp[k][j] + calc(i,k,j) )
\*************************/
for(int k=3;k<=n;k++){
for(int l=1,r=k;l<=n-k+1;l++,r++){
dp[l][r] = INF;
for(int mid=l+1;mid<r;mid++){
dp[l][r] = min(dp[l][r],dp[l][mid] + dp[mid][r] + ai[l] * ai[mid] * ai[r]);
}
}
}
cout<<dp[1][n]<<endl;
return;
}
}Q – 采药
这采药是什么时候加进来的？简单的OI背包。
#include<bits/stdc++.h>
using namespace std;
int dp[20000];
int t,m,ti[105],vi[105];
int main(){
memset(dp,-1,sizeof(dp));
cin>>t>>m;
dp[0]=0;
for(int i=0;i<m;i++){
cin>>ti[i]>>vi[i];
for(int j=t;j>=0;j--){
if(dp[j]!=-1 && dp[j]+vi[i]>dp[j+ti[i]]){
dp[j+ti[i]]=dp[j]+vi[i];
}
}
}
int ans=0;
for(int i=0;i<=t;i++){
if(dp[i]>ans){
ans=dp[i];
}
}
cout<<ans<<endl;
return 0;
}
