2415:Sashimi

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415

Monge DP。
週刊spaghetti_sourceさんにわかりやすい説明があったので参考にしながら解いた。
http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915

dp[ 左端 ][ 右端 ] := その部分を全て1cmに切るときの最小コスト
とすると、すでに1cmのときはコスト0だから
dp[ i ][ i ] = 0
区間[ i, j ]を[ i, r ]と[ r + 1, j ]に切るときは
dp[ i ][ j ] = min (dp[ i ][ r ]+dp[ r + 1 ][ j ]+cost[ i ][ j ])
となる。
このままだとO(n^3)で通らないが、cost[ i ][ j ]にはMonge性があってO(n^2)に落ちる。
K[ i ][ j ]=argmin (dp[ i ][ r ]+dp[ r + 1 ][ j ])
とすると
dp[ i ][ j ]={ min ( dp[ i ][ r ]+dp[ r + 1 ][ j ]) | K[ i ][ j - 1] <= r <= K[ i + 1 ][ j ] }

#include<iostream>
#include<vector>
#include<algorithm>
#define INF (1LL<<61)

using namespace std;

typedef unsigned long long ull;

int main(void){
	
	int n;
	cin >> n;
	
	ull cost[4001];
	for(int i=0;i<n;i++){
		cin >> cost[i];
		if(i>0)cost[i]+=cost[i-1];
	}
	
	static ull dp[4001][4001],k[4001][4001];
	fill(dp[0],dp[4001],INF);
	
	for(int i=0;i<n;i++)dp[i][i]=0,k[i][i]=i;
	
	for(int w=1;w<=n;w++){
		for(int i=0,j=i+w;j<n;i++,j++){
			for(int r=k[i][j-1];r<=k[i+1][j];r++){
				ull c=dp[i][r]+dp[r+1][j]+cost[j]-((i>0)?cost[i-1]:0);
				if(dp[i][j]>c)dp[i][j]=c,k[i][j]=r;
			}
		}
	}
	cout << dp[0][n-1] << endl;
	
	return 0;
}

3692:Kindergarten

問題文
http://poj.org/problem?id=3692
最大クリーク問題。

二部グラフになっているので補グラフの最大独立集合を求める。
最大クリーク=補グラフの最大独立集合
が成り立つ。また二部グラフなら、
最大独立集合=頂点数-最大マッチング
が成り立つ。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int V,match[401];
bool used[401];
vector<int>G[401];

void add_edge(int u,int v){
  G[u].push_back(v);
  G[v].push_back(u);
}

bool dfs(int v){
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    int u=G[v][i],w=match[u];
    if(w<0 || !used[w] && dfs(w)){
      match[v]=u;
      match[u]=v;
      return true;
    }
  }
  return false;
}

int bitpartite_matching(){
  int res=0;
  fill(match,match+401,-1);
  for(int v=0;v<V;v++){
    if(match[v]<0){
      fill(used,used+401,false);
      if(dfs(v))res++;
    }
  }
  return res;
}

int main(void){
  
  int g,b,m,t=1,graph[201][201];
  while(cin >> g >> b >> m,g|b|m){
    fill(graph[0],graph[201],0);
    for(int i=0;i<401;i++)G[i].clear();
    for(int i=0;i<m;i++){
      int l,r;
      cin >> l >> r;
      graph[l-1][r-1]=1;
    }

    for(int i=0;i<g;i++)
      for(int j=0;j<b;j++)
	if(graph[i][j]==0)add_edge(i,j+g);
	  
    V=g+b;
    cout << "Case " << t++ << ": " << g+b-bitpartite_matching() << endl;
  }
  
  return 0;
}