1083,1163

PKU難しいってつぶやいたら先輩が色んな問題の主観的難易度がのったページを教えてくれたので…

1083 Moving Tables

400部屋あり廊下を隔てて二列になっている。廊下は狭いので一つの机しか通らない。ある部屋からある部屋へ机を動かそうとしたとき、与えられた作業がすべて完了する最短時間を求めよ。ただし、一つの机を運ぶのに10分かかるとする。

方針

最初は400部屋の前をすでに通ったかで調べてWA.その後ちょこっとカンニングしてどうやら廊下単位で考えたらうまく行きそうなのでそのようにして貪欲でAC

コード

#include <cstdio>
#include <vector>
using namespace std;

int main() {
  int T; scanf("%d",&T);
  for (int ix=0; ix<T; ix++) {
    int N; scanf("%d",&N);
    vector<int> cor(200,0);
    int res=0;
    for (int i=0; i<N; i++) {
      int x,y; scanf("%d %d",&x,&y);
      if (x>y) swap(x,y);
      for (int j=(x-1)/2; j<=(y-1)/2; j++) cor[j]++;
    }
    for (int i=0; i<200; i++) if (res<cor[i]) res=cor[i];
    printf("%d\n",res*10);
  }
}

1163 The Triangle

三角形に数字が並んでいる。頂点から二分木のようにたどっていったとき最大の和を求めよ。

方針

最初DFSだと思って書いたけどTLE。その後子はその子に辿りつける親の最大値を足せばその子までの最大値になることに気づいたので、入力しながら同時にそれを処理するようにして、最後の探索はO(N)で完了。

コード

#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main() {
  int N; scanf("%d",&N);
  vvi tri;
  for (int i=1; i<=N; i++) {
    vi tmp(i);
    if (i!=1) {
      for (int j=0; j<i; j++) {
	scanf("%d",&tmp[j]);
	if (j==0) tmp[j]+=tri[i-2][j];
	else if (j==i-1) tmp[j]+=tri[i-2][j-1];
	else tmp[j]+=max(tri[i-2][j],tri[i-2][j-1]);
      }
    } else {
      scanf("%d",&tmp[0]);
    }
    tri.push_back(tmp);
  }
  int res=0;
  for (int i=0; i<N; i++) if (res<tri[N-1][i]) res=tri[N-1][i];
  printf("%d\n",res);
}