「AOJ2191～2200」の編集履歴（バックアップ）一覧に戻る
AOJ2191～2200 - (2013/01/25 (金) 15:21:24) のソース
*2199DD ifferential Pulse Code Modulation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199
差分パルス符号変調で音声信号を圧縮した時の元データとの差分の2乗和の最小値を求める問題。
解法
問題が簡単すぎます。
問題を読んで理解して書いてもこんなの15分で解けます。
まあ一歩進めて実際の圧縮計画を立てろといわれたら結構難問になりそうです。
何せ私3流高卒なものでそういった現実的な技術の世界は知らないのです。
#include<stdio.h>
#include<string.h>
int add(int num,int r){
num=num+r;
if(num<0)num=0;
if(num>255)num=255;
return num;
}
void calc(int n,int m){
int costs[260],nextCosts[260],codes[17],num;
memset(costs,-1,sizeof(costs));
costs[128]=0;
for(int i=0;i<m;i++)scanf("%d",&codes[i]);
for(int i=0;i<n;i++){
memset(nextCosts,-1,sizeof(nextCosts));
scanf("%d",&num);
for(int j=0;j<=255;j++){
if(costs[j]==-1)continue;
for(int k=0;k<m;k++){
int d=add(j,codes[k]);
int cost=(num-d)*(num-d)+costs[j];
if(nextCosts[d]==-1||nextCosts[d]>cost)nextCosts[d]=cost;
}
}
memcpy(costs,nextCosts,sizeof(nextCosts));
}
int ans=-1;
for(int i=0;i<=255;i++){
if(ans==-1||(costs[i]!=-1&&costs[i]<ans))ans=costs[i];
}
printf("%d\n",ans);
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0&&m==0)break;
calc(n,m);
}
}
*2200 Mr. Rito Post Office
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200
離島で勤務する郵便配達員が集配順序を守りながら町村を回るとき最短距離を求める問題。
ただし陸路と海路があり船を一隻だけ使える。
この問題は、市町村を一つ回ることを一段ずつ進めていく動的計画法で片が付きます。
状態としてはある市町村までの配達が終わり船が市町村Ziにあるという状態で区別し全ての場合での最短距離を求めていきこれを一段ずつ解いていくだけです。
計算はまず、全ての市町村間での陸路と海路をワーシャルフロイド法で個別に計算。
後はこの表を使って、陸路のみで目的地に辿りつけるか、船がP1にある状態から港町P2まで船で移動しそこから次の目的地にたどり着けるかを試していくだけです。
一度の移動では陸路のみ、陸路海路陸路という移動以外無意味なことを利用して解きます。
#include<stdio.h>
#include<string.h>
#include<algorithm>
void wf(int con[202][202],int n){
//ワーシャルフロイド法で陸路と海路の最小距離を求める
int t;
for(int y=1;y<=n;y++){
for(int x=1;x<=n;x++){
if(con[x][y]==-1)continue;
for(int i=1;i<=n;i++){
if(con[y][i]==-1)continue;
t=con[x][y]+con[y][i];
if(con[x][i]==-1||con[x][i]>t){
con[x][i]=con[i][x]=t;
}
}
}
}
}
void setData(int n,int m){
int conG[202][202],conM[202][202];//陸路と海路を表すグラフ-1なら接続なし
int ans[2][202];//ans[ターン][船の位置]
int x,y,t;
char sl[2];
memset(conG,-1,sizeof(conG));
memset(conM,-1,sizeof(conM));
memset(ans,-1,sizeof(ans));
for(int i=0;i<m;i++){
scanf("%d %d %d %s",&x,&y,&t,&sl);
if(sl[0]=='S'){
//海路
if(conM[x][y]==-1)conM[x][y]=conM[y][x]=t;
else conM[x][y]=conM[y][x]=std::min(t,conM[x][y]);
}else if(sl[0]=='L'){
//陸路
if(conG[x][y]==-1)conG[x][y]=conG[y][x]=t;
else conG[x][y]=conG[y][x]=std::min(t,conG[x][y]);
}
}
for(int i=1;i<=n;i++){
conG[i][i]=0;//今いる村から今いる村への移動は0
conM[i][i]=0;
}
wf(conG,n);
wf(conM,n);
int r,now,next,z,nowP=1;
scanf("%d",&r);
scanf("%d",&nowP);
ans[1][nowP]=0;
for(int i=1;i<r;i++){
now =i&1;
next=(i+1)&1;
memset(ans[next],-1,sizeof(ans[next]));
scanf("%d",&z);
for(int p1=1;p1<=n;p1++){
if(ans[now][p1]==-1)continue;
//陸路だけで到達できるか調べる
if(conG[nowP][z]!=-1){
if(ans[next][p1]==-1)ans[next][p1]=ans[now][p1]+conG[nowP][z];
else ans[next][p1]=std::min(ans[now][p1]+conG[nowP][z],ans[next][p1]);
}
//海路を通していく
for(int p2=1;p2<=n;p2++){
if(conM[p1][p2]==-1 || conG[nowP][p1]==-1 || conG[p2][z]==-1)continue;
int t=ans[now][p1]+conG[nowP][p1]+conM[p1][p2]+conG[p2][z];
if(ans[next][p2]==-1) ans[next][p2]=t;
else ans[next][p2]=std::min(ans[next][p2],t);
}
}
nowP=z;
}
int lastTime=2000000000;
for(int i=1;i<=n;i++){
if(ans[next][i]>-1)lastTime=std::min(lastTime,ans[next][i]);
}
printf("%d\n",lastTime);
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0&&m==0)break;
setData(n,m);
}
}
