richard-desktop

动态规划。我们先预处理出必要的区间段信息，然后发现其满足单调性，于是采用单调性优化。我们使用的是f(x)=min{f(i)+w(i,x)}这一经典模型，二分求出决策就可以了，总的复杂度是。

#include <cstdio>
#include <climits>
#include <cstring>
#include <stack>

using namespace std;

const int MAXN = 90+5;

struct status {
  int u,b,e;
  status(int _u,int _b,int _e)
    : u(_u),b(_b),e(_e) {}
  status() {}
};

char ma[MAXN],mb[MAXN];
int n,m,f[MAXN][MAXN],w[MAXN];
int p[MAXN][MAXN],r[MAXN],g[MAXN][MAXN];
stack<status> st[MAXN];
int tdec[MAXN];

int main() {
  int ncase;
  scanf("%d",&ncase);
  for (int loop = 1; loop<=ncase; loop++) {
    scanf("%d%d",&m,&n);
    scanf("%s%s",ma,mb);
    for (int i = 1; i<=n; i++)
      scanf("%d",&w[i]);
    for (int i = 1; i<=n; i++) {
      g[i][i] = w[i];
      for (int j = i+1; j<=n; j++)
        g[i][j] = g[i][j-1]+w[j]*(j-i+1);
    }
    f[0][0] = 0;
    st[1].push(status(1,1,n));
    for (int i = 1; i<=m; i++) {
      while (!st[i].empty()) {
        status tmp = st[i].top();
        for (int j = tmp.b; j<=tmp.e; j++)
          p[i][j] = tmp.u;
        st[i].pop();
      }
      for (int j = i; j<=n; j++)
        f[i][j] = f[i-1][p[i][j]-1]+g[p[i][j]][j];
      if (i<m) {
        st[i+1].push(status(i+1,i+1,n));
        for (int j = i+2; j<=n; j++) {
          while (!st[i+1].empty()) {
            int u = st[i+1].top().u;
            int b = st[i+1].top().b;
            if (j<=b && f[i][u-1]+g[u][b]>f[i][j-1]+g[j][b])
              st[i+1].pop();
            else break;
          }
          int u = st[i+1].top().u;
          int e = st[i+1].top().e;
          if (j<=e && f[i][u-1]+g[u][e]>f[i][j-1]+g[j][e]) {
            int l = st[i+1].top().b,r = e; // (]
            while (l+1<r) {
              int mid = (l+r)/2;
              if (j<=mid && f[i][u-1]+g[u][mid]>f[i][j-1]+g[j][mid]) r = mid;
              else l = mid;
            }
            st[i+1].top().e = l;
            st[i+1].push(status(j,l+1,n));
          }
          else if (e+1<=n) st[i+1].push(status(j,e+1,n));
        }
      }
    }
    for (int i = m,j = n; i>0; i--) {
      r[i] = p[i][j];
      j = r[i]-1;
    }
    r[m+1] = n+1;
    printf("Keypad #%d:\n",loop);
    for (int i = 1; i<=m; i++) {
      printf("%c: ",ma[i-1]);
      for (int j = r[i]; j<r[i+1]; j++)
        printf("%c",mb[j-1]);
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Your program in C++ from 2010-03-19 08:54:48 ran for 0.53 seconds and used 2792 KB of memory.

完整的题目描述在这里。

题目给了我们一些货物的价格a₁,...,a_m（不超过100000），要我们构造一种货币面值的方案x₁,...,x_n，使得所需要的纸币数量尽可能少。货币面值的方案必须满足

• x₁=1。
• 对于i<j，x_i一定是x_j的约数。

注意到不需要给出面值的方案，只是要求输出最少的张数，那么我们可以用动态规划解决。对于一个确定的方案，由于上述的性质，我们一定是用贪心的方法来付款。另外，价格不会超过100000，所以需要考虑的最大面值也是100000。对于一个面额x_i，付完款之后得到的余额是a₁%x_i,...,a_m%x_i。我们令f(i)表示用面值大于等于i的货币方案所付款所需要的纸币数量， 那么f(i)=min{f(j)+余额用i付款的张数 | i为j的约数}。具体的代码如下：

public class NewCoins {
  static final int MAXN = 100000;
  public int minCoins(int[] price) {
    int n = price.length;
    int[] f = new int[MAXN+1];
    for (int i = MAXN; i>0; i--) {
      for (int j = 0; j<n; j++)
        f[i] += price[j]/i;
      for (int j = 2*i; j<=MAXN; j += i) {
        int tmp = f[j];
        for (int k = 0; k<n; k++)
          tmp += (price[k]%j)/i;
        if (f[i]>tmp) f[i] = tmp;
      }
    }
    return f[1];
  }
}

至此，问题就解决了。