月度归档:2019年06月

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;
}

HDU 1069 Monkey and Banana

Monkey and Banana

dp[i][j][k]:堆i个箱子,最底下的箱子为第j个,且该箱子为第k个姿态(长x,宽y,高z的组合).

状态转移方程见代码.

其实可以把同一种箱子的不同姿态当作不同的箱子存进去,然后状态转移的时候直接比较x和y,状态转移那里就不用写那么繁琐了.

#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 dp[91][35][3];
int a[35][3];
int t[35][3];

int main() {
  int n, k = 0;
  while (cin >> n && n) {
    int ans = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; ++i) {
      cin >> a[i][0] >> a[i][1] >> a[i][2];
      sort(a[i], a[i] + 3);
      dp[1][i][0] = a[i][0];
      dp[1][i][1] = a[i][1];
      dp[1][i][2] = a[i][2];
      ans = max(ans, dp[1][i][0]);
      ans = max(ans, dp[1][i][1]);
      ans = max(ans, dp[1][i][2]);
    }
    for (int i = 2; i <= n * 3; ++i) {
      for (int j = 1; j <= n; ++j) {
        for (int k = 1; k <= n; ++k) {
          if (a[j][1] > a[k][1] && a[j][2] > a[k][2])
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] + a[j][0]);
          if (a[j][1] > a[k][0] && a[j][2] > a[k][2])
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][1] + a[j][0]);
          if (a[j][1] > a[k][0] && a[j][2] > a[k][1])
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][2] + a[j][0]);
          if (a[j][0] > a[k][1] && a[j][2] > a[k][2])
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][0] + a[j][1]);
          if (a[j][0] > a[k][0] && a[j][2] > a[k][2])
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][1] + a[j][1]);
          if (a[j][0] > a[k][0] && a[j][2] > a[k][1])
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][2] + a[j][1]);
          if (a[j][0] > a[k][1] && a[j][1] > a[k][2])
            dp[i][j][2] = max(dp[i][j][2], dp[i - 1][k][0] + a[j][2]);
          if (a[j][0] > a[k][0] && a[j][1] > a[k][2])
            dp[i][j][2] = max(dp[i][j][2], dp[i - 1][k][1] + a[j][2]);
          if (a[j][0] > a[k][0] && a[j][1] > a[k][1])
            dp[i][j][2] = max(dp[i][j][2], dp[i - 1][k][2] + a[j][2]);
          ans = max(ans, dp[i][j][0]);
          ans = max(ans, dp[i][j][1]);
          ans = max(ans, dp[i][j][2]);
        }
      }
    }
    printf("Case %d: maximum height = %d\n", ++k, ans);
  }
  return 0;
}

HDU 1024 Max Sum Plus Plus

HDU 1024

dp[i][j]:前j个数的最大i子段和,且最后一段以第j个数结尾.
状态转移方程: dp[i][j]=max(dp[i][j-1]+a[j] , max{ dp[i-1][k] } + a[j] ) 0<k<j
max{dp[i-1][k]}在上一轮计算的时候可以确定, 于是提前记录下来,如此时间复杂度为O(N^2).
然后可以用滚动数组优化,防止爆数组.

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

int a[1000005];
ll dp[1000005];
ll max_last[1000005];

int main() {
  int n, m;
  while (~scanf("%d%d",&m,&n)) {
    memset(dp,0,sizeof(dp));
    memset(max_last,0,sizeof(max_last));
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
    }
    ll ans = 0,maxx;
    for (int i = 1; i <= m; ++i) {
      maxx=-maxn;
      for (int j = i; j <= n; ++j) {
        dp[j] = max(max_last[j-1], dp[j - 1]) + a[j];
        max_last[j-1]=maxx;
        maxx=max(dp[j],maxx);
      }
    }
   printf("%lld\n",maxx);
  }
  return 0;
}

洛谷P1908 逆序对

洛谷 P1908

以前用树状数组求逆序对,现在用归并排序写一下,顺便复习一下归并排序.

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

int a[500005];
int b[500005];
ll cnt;
void merge(int l,int mid,int r){
  int i=l,j=mid+1;
  for(int k=l;k<=r;++k){
    if(j>r||i<=mid&&a[i]<=a[j]) b[k]=a[i++];
    else b[k]=a[j++],cnt+=mid-i+1;
  }
   for(int k=l;k<=r;++k) a[k]=b[k];
}

void mergeSort(int l, int r){
  if(l<r){
       int mid=(l+r)>>1;
       mergeSort(l,mid);
       mergeSort(mid+1,r);
       merge(l,mid,r);
  }  
}

int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    scanf("%d",&a[i]);
  }
  mergeSort(1,n);
  cout<<cnt<<endl;
  return 0;
}

洛谷P1880 [NOI1995]石子合并

洛谷P1880 石子合并

区间dp模板题.
注意石子是环形放置的.

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 0x3f3f3f3f
using namespace std;

int dp1[205][205];
int dp2[205][205];
int a[205];
int s[205];
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    a[i+n]=a[i];
  }
  for(int i=1;i<=n+n;++i){
    s[i]=s[i-1]+a[i];
  }
  for(int len=2;len<=n;++len){
     for(int i=1;i<=n+n+1-len;++i){
       int j=i+len;
       dp1[i][j]=maxn;
       for(int k=i+1;k<j;++k){
         dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k][j]+s[j-1]-s[i-1]);
         dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k][j]+s[j-1]-s[i-1]);
       }
     }
  }
  int ans1=maxn,ans2=0;
  for(int i=1;i<=n;++i){
    ans1=min(dp1[i][i+n],ans1);
    ans2=max(dp2[i][i+n],ans2);
  }
  cout<<ans1<<endl;
  cout<<ans2<<endl;
  return 0;
}

洛谷P1280 尼克的任务

洛谷P1280 尼克的任务

dp[i]:从第i分钟开始到第N分钟的最大空闲时间.
当第i分钟无开始的任务,dp[i]=dp[i+1]+1;
否则,dp[i]=max{ dp[ i+t[j] ] }, t[j]为第i分钟开始的任务的持续时间.
然后逆推...

关于顺推的尝试(dp[i]:从第1分钟开始到第i分钟的最大空闲时间):
如果将结束时间排下序,然后顺推,就不行,因为不一定会选择在该时刻结束的任务.

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int dp[10005];
struct T{
  int p,t;
  bool operator< (const T &a){
    return p<a.p;
  }
}a[10005];

int main(){
  int n,k;
  cin>>n>>k;
  for(int i=0;i<k;++i){
    cin>>a[i].p>>a[i].t;
  }
  sort(a,a+k);
  for(int i=n,j=k-1;i>=1;--i){
      if(i!=a[j].p){
       dp[i]=dp[i+1]+1;
      }
      else{
        while(j>=0&&i==a[j].p){
          dp[i]=max(dp[i+a[j].t],dp[i]);
          j--;
        }
      }
  }
  cout<<dp[1]<<endl;
  return 0;
}

洛谷P1091 合唱队形

两趟最长上升子序列dp,枚举中间的人求队伍长度最大值,然后总人数减去它就行了.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int n;
int a[105];
int dp1[105];
int dp2[105];
int ans;
int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    dp1[i]=1;
    for (int k = 1; k < i; ++k) {
      if (a[k] < a[i]) {
        dp1[i] = max(dp1[k] + 1, dp1[i]);
      }
    }
  }
  for (int j = n; j >= 1; --j) {
    dp2[j]=1;
    for (int k = n; k >= j; --k) {
      if (a[k] < a[j]) {
        dp2[j] = max(dp2[k] + 1, dp2[j]);
      }
    }
  }
  for(int i=1;i<=n;++i){
      ans=max(ans,dp1[i]+dp2[i]-1);
  }
  cout << n-ans << endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}

洛谷P1020 导弹拦截

洛谷P1020

O(logN)做法:
dp1[i]:=长度为i的非升子序列中末尾元素的最大值
dp2[i]:=长度为i的上升子序列中末尾元素的最小值

注意
dp1中元素可以相等,用upper_bound搜索替换位置.
dp2中元素不可以相等,用lower_bound搜索替换位置.

可参考<<挑战程序设计竞赛>>P65

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int t[100005];
int dp1[100005];
int dp2[100005];
int ans1, ans2;
int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);

  int n = 0;
  while (cin >> t[++n]);
  n--;
 /* O(n^2) 
  for (int j = 1; j <= i; ++j) {
    for (int k = 0; k < j; ++k) {
      if (t[k] >= t[j] || k == 0) dp1[j] = max(dp1[j], dp1[k] + 1);
      if (t[k] < t[j]) dp2[j] = max(dp2[k] + 1, dp2[j]);
      ans1 = max(dp1[j], ans1);
      ans2 = max(dp2[j], ans2);
    }
  }
  cout << ans1 << endl;
  cout << ans2 << endl;
 */

 //O(logN)
 for(int i=1;i<=n;++i){
     dp2[i]=maxn;
 }
  for(int i=1;i<=n;++i){
      *upper_bound(dp1+1,dp1+n+1,t[i],greater<int>())=t[i];
      *lower_bound(dp2+1,dp2+n+1,t[i])=t[i];
  }
  ans1=lower_bound(dp1+1,dp1+n+1,0,greater<int>() )-(dp1+1);
  ans2=lower_bound(dp2+1,dp2+n+1,maxn)-(dp2+1);
  cout<<ans1<<endl;
  cout<<ans2<<endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}

洛谷P1019 单词接龙

预处理单词i连接单词j的最小重叠部分,然后dfs即可.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int ex[25][25];
string s[25];
int n;
void pre() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int len1 = s[i].length();
      int len2 = s[j].length();
      for (int k = 1; k <= len1 - 1; ++k) {
        int m = 0;
        for (; m < len2 - 1 && m < k; ++m) {
          if (s[i][len1 - k + m] != s[j][m]) {
            break;
          }
        }
        if (m == k && m < len2 - 1) {
          ex[i][j] = k;
          break;
        }
      }
    }
  }
}
int vis[25];
int ans;

void dfs(int i, int len) {
  vis[i]++;
  // cout<<i<<endl;
  int j = 0;
  for (j = 0; j < n; ++j) {
    if (ex[i][j] && vis[j] < 2) {
      dfs(j, len + s[j].length() - ex[i][j]);
      vis[j]--;
    }
  }
  if (j == n) ans = max(ans, len);
}

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
  char a;
  cin >> a;
  pre();
  for (int i = 0; i < n; ++i) {
    if (s[i][0] == a) {
      dfs(i, s[i].length());
      vis[i]--;
    }
  }
  cout << ans << endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}

BZOJ1697 Cow Sorting (置换群)

分析可参考 :
http://hzwer.com/3905.html

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int pos[100005];
int a[10005];
int vis[10005];

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n,smallest=100000;
  cin>>n;
  for(int i=1;i<=n;++i){
      cin>>a[i];
      pos[a[i]]=i;
      smallest=min(a[i],smallest);
  }
  sort(a+1,a+1+n);
  int ans=0;
  for(int i=1;i<=n;++i){
      int p=i;
      int len=0,sum=0,minn=a[p];
      while(!vis[p]){
          vis[p]=1;
          sum+=a[p];
          len++;
          minn=min(minn,a[p]);
          p=pos[a[p]];
      }
      if(len) ans+= min(sum+minn+(len+1)*smallest,sum+(len-2)*minn);
  }
  cout<<ans<<endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}