2013年5月31日

UVa 245 - Uncompress

#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <set>
using namespace std;

int main() {
  char tmp[9999];
  string s;
  int first = 1;
  while (gets(tmp) && string(tmp) != "0") {
    if (!first) s.append("\n");
    s.append(tmp);
    first = 0;
  }
  vector<string> words;
  set<string> dic;
  string temp;
  for (int i = 0, j; s[i]; i++)
    if ('0' <= s[i] && s[i] <= '9') {
      int num = 0;
      while (isdigit(s[i])) {
        num = num * 10 + (s[i] - '0');
        i++;
      }
      i--;
      temp = words[words.size() - num];
      words.erase(words.begin() + words.size() - num);
      words.push_back(temp);
      printf("%s", temp.c_str());
      temp = "";
    } else {
      putchar(s[i]);
      if (isalpha(s[i])) {
        temp.insert(temp.end(), s[i]);
      } else if (temp.length()) {
        if (!dic.count(temp)) {
          dic.insert(temp);
        } else {
          for (j = 0; j < words.size(); j++)
            if (words[j] == temp) break;
          words.erase(words.begin() + j);
        }
        words.push_back(temp);
        temp = "";
      }
    }
  puts("");
  return 0;
}

2013年5月20日

UVa 10003 - Cutting Sticks


#include <stdio.h>

int main() {
  int len;
  while (scanf("%d", &len) && len) {
    int n, pos[99], dp[99][99];
    scanf("%d", &n);
    int i, j, k, l;
    for (i = 1; i <= n; i++)
      scanf("%d", &pos[i]);
    pos[0] = 0;
    pos[n + 1] = len;
    for (k = 2; k <= n + 1; k++)
      for (i = 0; i <= n - k + 1; i++) {
        j = i + k;
        dp[i][j] = 1e9;
        for (l = i + 1; l < j; l++) {
          int cost = dp[i][l] + dp[l][j] + pos[j] - pos[i];
          dp[i][j] = dp[i][j] < cost ? dp[i][j] : cost;
        }
      }
    printf("The minimum cutting is %d.\n", dp[0][n + 1]);
  }
  return 0;
}

2013年5月17日

UVa 10910 - Marks Distribution


#include <stdio.h>

int main() {
  int i, j, k;
  long long dp[99][99] = {1};
  for (i = 1; i <= 70; i++)
    for (j = 0; j <= 70; j++)
      for (k = j; k >= 0; k--)
        dp[i][j] += dp[i - 1][j - k];
  int n, t, p, C;
  scanf("%d", &C);
  while (C--) {
    scanf("%d%d%d", &n, &t, &p);
    t -= n * p;
    printf("%lld\n", t >= 0 ? dp[n][t] : 0);
  }
  return 0;
}