分类目录归档:动态规划

Kick Start 2018 Round B B题

Sherlock and the Bit Strings

构造一个长度为N的只有‘0’和‘1’的串s,满足K个限制(s[A,B]中含有C个1),且这个串在所有满足限制的合法串当中为字典序第P大.

状压dp,f[i][j]:假设前i个字符已固定,且这前i个中最后16个字符为j时的合法方案数(注意j前面的到底是什么我们不用管,反正看作前缀是固定的,而这个结果统计的是前缀之后的部分可以有多少种变化)。我们从后往前转移,最终得到每个位置的情况。如何转移看代码就很清楚了,再次感到熟练位操作对做状压方面的题目很重要。

官方题解开头就讲到固定前缀的合法方案数与字典序第p大的关系,一开始没理解...就是如果串是i开头的话(我们以字典序的顺序来尝试i),f[1][i]>=p,那么第p大就一定是在这f[1][i]方案中了,否则从P中减掉f[1][i](f[1][i]的方案里都是些比P小的啊,减掉f[1][i]之后的P(用P'表示吧)就是开头字典序比i大时的方案里第p'大的,也是原来那个第P大的),i再转向下一个字典序更大的选择。然后可以一个一个位置构造出这个串。

#include<bits/stdc++.h>
using namespace std;

long long f[105][1<<16];
vector <pair<int,int> > limits[105];
int cnt[1<<16];
int shl[1<<16];

bool check(int i,int last){
    for(int j=0;j<limits[i].size();++j){
        if(cnt[((1<<limits[i][j].first)-1)&last]!=limits[i][j].second){
            return false;
        }
    }
    return true;
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    for(int i=1;i<(1<<16);++i){
        cnt[i]=cnt[i>>1]+(i&1);
        shl[i]=(i<<1)&((1<<16)-1);
    }
    while(T--){
        int n,k;
        long long p;
        scanf("%d%d%lld",&n,&k,&p);
        for(int i=1;i<=n;++i) limits[i].clear();
        for(int i=1;i<=k;++i){
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            limits[B].push_back(make_pair(B-A+1,C));
        }
        for(int i=0;i<(1<<16);++i){
            if(check(n,i)){
                f[n][i]=1;
            }
            else f[n][i]=0;
        }
        for(int i=n-1;i>0;--i){
            for(int j=0;j<(1<<16);++j){
                if(check(i,j)){
                    f[i][j]=f[i+1][shl[j]]+f[i+1][shl[j]^1];
                    if(f[i][j]>1e18) f[i][j]=1e18+1;
                }
                else f[i][j]=0;
            }
        }

        printf("Case #%d: ",++kase);
        for(int i=1,j=0;i<=n;++i,j=shl[j]){
            if(f[i][j]>=p){
                printf("0");
            }
            else{
                p-=f[i][j];
                j^=1;
                printf("1");
            }
        }
        printf("\n");

    }
    return 0;
}

Comet OJ 双倍快乐

双倍快乐

f[i][j]: 两个子序列分别以i和j结尾时的最大和.
LIS的变形,每次可将第k个元素尝试添加到两个序列里.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int a[505];
int f[505][505];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  int ans=0;
  for(int k=1;k<=n;++k){
    for(int i=0;i<k;++i){
      for(int j=0;j<k;++j){
          if(a[k]>=a[i]) {
            f[k][j]=max(f[k][j],f[i][j]+a[k]);
          }
          if(a[k]>=a[j]){
            f[i][k]=max(f[i][k],f[i][j]+a[k]);
          }
      }
    }
  }
  for(int i=0;i<=n;++i){
    for(int j=0;j<=n;++j){
      ans=max(ans,f[i][j]);
    }
  }
  cout<<ans<<endl;
  return 0;
}

POJ – 3186 Treats for the Cows

题目链接

f[i][j]:只剩第i个到第j个时,将其取完获得的最大价值.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int f[2005][2005];
int a[2005];
int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    f[i][i]=n*a[i];
  }
  for(int i=1;i<n;++i){
      for(int l=1;l+i<=n;++l){
        int r=l+i;
        f[l][r]=max(f[l+1][r]+(n-i)*a[l],f[l][r-1]+(n-i)*a[r]);
      }
  }
  cout<<f[1][n]<<endl;
  return 0;
}

POJ – 1661 Help Jimmy

题目链接

f[i][0]:从i平台左端跳下到地面的最短时间(不包括竖直距离)
f[i][1]:从j平台右端跳下到地面的最短时间(不包括竖直距离)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
struct level {
  int x1, x2, h;
} a[1005];

bool cmp(level a, level b) { return a.h > b.h; }

long long f[1005][2];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, N, X, Y, MAX;
  cin >> T;
  while (T--) {
    cin >> N >> X >> Y >> MAX;
    for (int i = 1; i <= N; i++) {
      cin >> a[i].x1 >> a[i].x2 >> a[i].h;
    }
    //起点
    a[0].x1 = X;
    a[0].x2 = X;
    a[0].h = Y;
    //地面
    a[N + 1].x1 = -INF;
    a[N + 1].x2 = INF;
    a[N + 1].h = 0;
    sort(a + 1, a + 1 + N, cmp);  //从高到低排序
    for (int i = N; i >= 0; --i) {
      int j;
      //从i的左端跳下
      for (j = i + 1; j <= N + 1; ++j) {
        if (a[j].x1 <= a[i].x1 && a[i].x1 <= a[j].x2) {
          break;
        }
      }
      if (j == N + 1) {
        if (a[i].h <= MAX)
          f[i][0] = 0;
        else
          f[i][0] = INF;
      } else {
        if (a[i].h - a[j].h <= MAX) {
          int t1 = a[i].x1 - a[j].x1 + f[j][0];
          int t2 = a[j].x2 - a[i].x1 + f[j][1];
          f[i][0] = min(t1, t2);
        } else
          f[i][0] = INF;
      }
      //从i的右端跳下
      for (j = i + 1; j <= N + 1; ++j) {
        if (a[j].x1 <= a[i].x2 && a[i].x2 <= a[j].x2) {
          break;
        }
      }
      if (j == N + 1) {
        if (a[i].h <= MAX)
          f[i][1] = 0;
        else
          f[i][1] = INF;
      } else {
        if (a[i].h - a[j].h <= MAX) {
          int t1 = a[i].x2 - a[j].x1 + f[j][0];
          int t2 = a[j].x2 - a[i].x2 + f[j][1];
          f[i][1] = min(t1, t2);
        } else
          f[i][1] = INF;
      }
    }
    cout << f[0][0] + Y << endl;
  }
  return 0;
}

POJ – 1015 Jury Compromise

POJ 1015
f[i][j][k]:从前i个人中选j个人,辩控差为k时的最大辩控和

状态转移即在第i(i<=j)个阶段,要么选第i个人,要么不选第i个人.
其实是个01背包.
注意下标范围,防负数出现.
嗯...代码写得挫,先这样吧.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include<cstring>
using namespace std;

int p[201], d[201];
int f[201][21][801];
int P, D, N, M;
int ans[21];

struct Path {
  int n, m, k, id;
} path[201][21][801];

void goBack(int n, int m, int k) { //状态回溯 
  int cnt = 0;
  while (path[n][m][k].id) {
    int next_n = path[n][m][k].n;
    int next_m = path[n][m][k].m;
    int next_k = path[n][m][k].k;
    if (path[n][m][k].id != path[next_n][next_m][next_k].id)
      ans[cnt++] = path[n][m][k].id;
    n = next_n, m = next_m, k = next_k;
  }
}

int main() {
  int kase = 0;
  while (cin >> N >> M && N&&M) {
    for (int i = 1; i <= N; ++i) {
      cin >> p[i] >> d[i];
    }
    P = 0, D = 0;
    memset(f,-1,sizeof(f));
    path[0][0][400].id=0;
    f[0][0][400] = 0;
    for (int i = 1; i <= N; ++i) {
      for (int j = 0; j <= M; ++j) {
        for (int k = -400; k <= 400; ++k) {
          if (j > 0 && k + p[i]-d[i] + 400 >= 0 && k + p[i]-d[i] + 400 <= 800 &&
              f[i - 1][j - 1][k + 400] != -1 &&
              f[i][j][k + p[i]-d[i] + 400] < f[i - 1][j - 1][k + 400] + p[i]+d[i]) {
            f[i][j][k + 400 + p[i]-d[i]] = f[i - 1][j - 1][k + 400] + p[i]+d[i];
            path[i][j][k + 400 + p[i]-d[i]].id = i;
            path[i][j][k + 400 + p[i]-d[i]].k = k + 400;
            path[i][j][k + 400 + p[i]-d[i]].m = j - 1;
            path[i][j][k + 400 + p[i]-d[i]].n = i - 1;
          }
          if (f[i - 1][j][k + 400] != -1 &&
              f[i - 1][j][k + 400] > f[i][j][k + 400]) {
            f[i][j][k + 400] = f[i - 1][j][k + 400];
            path[i][j][k + 400].id = path[i - 1][j][k + 400].id;
            path[i][j][k + 400].k = k + 400;
            path[i][j][k + 400].m = j;
            path[i][j][k + 400].n = i - 1;
          }
        }
      }
    }
    for (int k = 0; k <= 400; ++k) {
      if (f[N][M][400 + k] != -1 || f[N][M][400 - k] != -1) {
        if (f[N][M][400 + k] > f[N][M][400 - k]) {
          goBack(N, M, k + 400);
          P = (f[N][M][400 + k] + k) / 2;
          D = (f[N][M][400 + k] - k) / 2;
        } else {
          goBack(N, M, 400 - k);
          P = (f[N][M][400 - k] - k) / 2;
          D = (f[N][M][400 - k] + k) / 2;
        }
        printf("Jury #%d\n", ++kase);
        printf(
            "Best jury has value %d for prosecution and value %d for "
            "defence:\n",
            P, D);
        for (int i = M - 1; i >= 0; --i) {
          printf(" %d", ans[i]);
        }
        printf("\n");
        break;
      }
    }
  }
  return 0;
}

HDU – 1260 Tickets

HDU 1260

又是一道简单DP...
轮到第i个人的时候,要么是单独一人买,要么是和前面一个人组团买.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int n;
int k;
int a[2005];
int b[2005];
int f[2005];
int main() {
  cin>>n;
  while(n--){
    cin>>k;
    for(int i=1;i<=k;++i){
      cin>>a[i];
    }
    for(int i=1;i<=k-1;++i){
      cin>>b[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=k;++i){
      f[i]=min(f[i],f[i-1]+a[i]);
      if(i>=2) f[i]=min(f[i],f[i-2]+b[i-1]);
    }
    int s=f[k]%60;
    int m=f[k]/60%60;
    int h=f[k]/60/60;
    char state[]="am";
    if(8+h>12) state[0]='a',h-=12;
    printf("%02d:%02d:%02d %s\n",8+h,m,s,state);
  }
  return 0;
}

HDU 1176 免费馅饼

HDU 1176

每个状态都有三种转移的选择,即向左\向右\停留,注意不能到达的位置.

看到很多人是用逆推做的,自己去年做的时候看别人的题解也是用逆推做的,现在重新用顺推做了一遍.

顺推的做法:f[i][j]表示从开始到第i秒,以第j个位置为终点最多有几个馅饼. 结果是max{f[end][j]}.
逆推的做法:f[i][j]表示第i秒开始,以第j个位置为起点,到最后一秒最多有几个馅饼. 结果是f[0][5].

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int n;
int a[100005][12];
int f[100005][12];
int pos[100005][12];
int main() {
  while (cin>>n&&n) {
      memset(a,0,sizeof(a));
      memset(f,0,sizeof(f));
      memset(pos,0,sizeof(pos));
      int maxT=0;
      for(int i=0;i<n;++i){
          int x,t;
          scanf("%d%d",&x,&t);
          a[t][x]++;
          maxT=max(t,maxT);
      }
      pos[0][5]=1;
      for(int i=1;i<=maxT;++i){
        for(int j=0;j<=10;++j){
          if(pos[i-1][j]){
            pos[i][j]=pos[i][j+1]=pos[i][j-1]=1;
            f[i][j]=max(f[i][j],a[i][j]+f[i-1][j]);
            if(j+1<=10&&f[i][j+1]<f[i-1][j]+a[i][j+1]){
              f[i][j+1]=f[i-1][j]+a[i][j+1];
            }
            if(j-1>=0&&f[i][j-1]<f[i-1][j]+a[i][j-1]){
              f[i][j-1]=f[i-1][j]+a[i][j-1];
            }
          }
        }
      }
      int ans=0;
      for(int i=0;i<=10;++i){
        ans=max(ans,f[maxT][i]);
      }
      printf("%d\n",ans);
  }
  return 0;
}

HDU – 1114 Piggy-Bank (完全背包)

HDU 1114

应该是完全背包裸题吧,第一次练习...

与01背包不同的是,j的正序循环保证了在同一个阶段之间的状态转移,即同一个物品可以使用多次.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int n;
int w[505];
int v[505];
ll f[10005];

int main() {
  int T;
  cin>>T;
  while (T--) {
     for(int i=0;i<10005;++i){
       f[i]=maxn;
     }
     int E,F;
     scanf("%d%d",&E,&F);
     int W=F-E;
     scanf("%d",&n);
     for(int i=0;i<n;++i){
       scanf("%d%d",&v[i],&w[i]);
     }
     f[0]=0;
    for(int i=0;i<n;++i){
      for(int j=w[i];j<=W;++j){
          f[j]=min(f[j],f[j-w[i]]+v[i]);
      }
    }
    if(f[W]==maxn){
       printf("This is impossible.\n");
    }
    else{
      printf("The minimum amount of money in the piggy-bank is %lld.\n",f[W]);
    }

  }
  return 0;
}

HDU – 1074 Doing Homework (状态压缩dp)

HDU 1074

状态转移方程:
当currutTime+consume[k]-deadline[k]>0,
f[i|(1<<k)] = min( f[i|(1<<k)] , f[i]+currentTime+comsume[k]-deadline[k] );
否则,
f[i|(1<<k)] = min( f[i|(1<<k)] , f[i] );

i表示已经完成的作业情况,k表示第k个作业。对同一个状态 m=(i|(1<<k)),i和k的组合能有多种, 因为输入是按字典序给出的,让到达m时i尽量小,则能保证输出是字典序最小(即i从小到大遍历)。

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int f[1 << 15];
int t[1 << 15];
int pre[1<<15];
int n;
struct homework {
  string s;
  int D;
  int C;
} a[20];

void print(int m) {
   if(m) {
    for(int i=0;i<n;++i){
      if((1<<i)&(m-pre[m])){
        print(pre[m]);
        cout<<a[i].s<<endl;
        break;
      }
    }
  }
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> a[i].s >> a[i].D >> a[i].C;
    }
    memset(t, 0x3f, sizeof(t));
    memset(f, 0x3f, sizeof(f));
    t[0] = 0;
    f[0] = 0;
    for (int i = 0; i < (1 << n); ++i) {
      for (int k = 0; k < n; ++k) {
        if ((i &(1 << k) )==0) {
          if ((t[i] + a[k].C >= a[k].D)) {
            if (f[i|(1<<k)] > f[i] + t[i] + a[k].C - a[k].D) {
              f[i|(1<<k)] = f[i] + t[i] + a[k].C - a[k].D;
              t[i|(1<<k)] = t[i] + a[k].C;
              pre[i|(1<<k)] = i;
            }
          } else {
            if (f[i|(1<<k)] > f[i]) {
              f[i|(1<<k)] = f[i];
              t[i|(1<<k)] = t[i] + a[k].C;
              pre[i|(1<<k)] = i;
            }
          }
        }
      }
      //cout<<f[i]<<" "<<t[i]<<endl;
    }
    cout << f[(1 << n) - 1] << endl;
    print((1 << n) - 1);
  }
  return 0;
}

POJ 2411 Mondriaan’s Dream (状态压缩dp)

POJ2411

《算法竞赛进阶指南》P298 状态压缩DP例题

所谓状态压缩DP,就是通过二进制数来记录状态集合,这个二进制数作为DP的维度。

#include<iostream>
using namespace std;
typedef long long ll;

int n,m;
ll f[12][1<<11];
bool in_s[1<<11];

int main(){
    while(cin>>n>>m&&n){
        for(int i=0;i<1<<m;++i){
            bool cnt=0,has_odd=0;//has_odd:已经出现一段奇数个连续的0,cnt:当前是否出现了奇数个0
            for(int j=0;j<m;++j){
                if(i>>j&1) has_odd|=cnt,cnt=0;
                else cnt^=1;
            }
            in_s[i]=has_odd|cnt?0:1;
        }
        f[0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<1<<m;++j){
                f[i][j]=0;
                for(int k=0;k<1<<m;++k){
                    if((j&k)==0&&in_s[j|k]){
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
        cout<<f[n][0]<<endl;

    }
    return 0;
}