AOJ 1311,2305

500 点を埋める

1311:
Dijkstraするだけ。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int ijk[100][100];
bool v[100][100];
vector<pair<int,int> >g[100];
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a){
		for(int i=0;i<a;i++)g[i].clear();
		for(int i=0;i<b;i++){
			int d,e,f;
			scanf("%d%d%d",&d,&e,&f);
			g[d-1].push_back(make_pair(e-1,f));
		}
		for(int i=0;i<a;i++)
			for(int j=0;j<a;j++){
				ijk[i][j]=999999999;
				v[i][j]=false;
			}
		priority_queue<pair<int,pair<int,int> > >Q;
		Q.push(make_pair(0,make_pair(0,0)));
		ijk[0][0]=0;
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int val=Q.top().second.second;
			Q.pop();
			if(v[at][val])continue;
			v[at][val]=true;
			for(int i=0;i<g[at].size();i++){
				if(!v[g[at][i].first][val]&&ijk[at][val]+g[at][i].second<ijk[g[at][i].first][val]){
					ijk[g[at][i].first][val]=ijk[at][val]+g[at][i].second;
					Q.push(make_pair(-ijk[g[at][i].first][val],make_pair(g[at][i].first,val)));
				}
				if(val<a-1&&!v[g[at][i].first][val+1]&&ijk[at][val]<ijk[g[at][i].first][val+1]){
					ijk[g[at][i].first][val+1]=ijk[at][val];
					Q.push(make_pair(-ijk[g[at][i].first][val+1],make_pair(g[at][i].first,val+1)));
				}
			}
		}
		for(int i=0;i<a;i++)if(ijk[a-1][i]<=c){
			printf("%d\n",i);break;
		}
	}
}

2305
logのDP。

#include<stdio.h>
#include<algorithm>
using namespace std;
double dp[20][200000];
int b[20];
int ABS(int a){return max(a,-a);}
int main(){
    int a;
    scanf("%d",&a);
    for(int i=0;i<a;i++)scanf("%d",b+i);
    for(int i=0;i<a;i++)
        for(int j=0;j<200000;j++)
            dp[i][j]=999999999;
    for(int i=1;i<200000;i++)
        dp[0][i]=(double)ABS(i-b[0])/b[0];
    for(int i=0;i<a-1;i++){
        for(int j=1;j<200000;j++){
            for(int k=j;k<200000;k+=j)dp[i+1][k]=min(dp[i+1][k],max(dp[i][j],(double)ABS(k-b[i+1])/b[i+1]));
        }
    }
    double ret=999999999;
    for(int i=0;i<200000;i++)ret=min(ret,dp[a-1][i]);
    printf("%.9f\n",ret);
}