2199DD ifferential Pulse Code Modulation
解法
問題が簡単すぎます。
問題を読んで理解して書いてもこんなの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
この問題は、市町村を一つ回ることを一段ずつ進めていく動的計画法で片が付きます。
状態としてはある市町村までの配達が終わり船が市町村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);
}
}
最終更新:2013年01月25日 15:21