poj 2686 Traveling by Stagecoach
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=8+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int n,m,p,a,b;
int t[MAX_N];
int edge[MAX_M][MAX_M];
double dp[1<<MAX_N][MAX_M];
int main()
{
while(~scanf("%d%d%d%d%d",&n,&m,&p,&a,&b))
{
if(n==0&&m==0&&p==0&&a==0&&b==0)
break;
int i;
me(edge,-1);
for(i=0; i<=(1<<n); i++)
{
fill(dp[i],dp[i]+1+m,1.0*inf);
}
for(i=1; i<=n; i++)
{
scanf("%d",&t[i]);
}
for(i=1; i<=p; i++)
{
int l,r,value;
scanf("%d%d%d",&l,&r,&value);
edge[l][r]=value;
edge[r][l]=value;
}
dp[(1<<n)-1][a]=0;
double mn=1.0*INF;
for(i=(1<<n)-1; i>=0; i--)
{
for(int s=1; s<=n; s++)
if((i>>(s-1))&1)
{
for(int u=1; u<=m; u++)
{
for(int v=1; v<=m; v++)
{
if(edge[u][v]>=0)
{
//cout<<u<<' '<<v<<' '<<i<<' '<<(i^(1<<(s-1)))<<' '<<dp[i^(1<<(s-1))][v]<<' '<<dp[i][u]+1.0*edge[u][v]/t[s]<<endl;
dp[i^(1<<(s-1))][v]=min(dp[i^(1<<(s-1))][v],dp[i][u]+1.0*edge[u][v]/t[s]);
//cout<<dp[i^(1<<(s-1))][v]<<endl;
//cout<<(i^(1<<(s-1)))<<' '<<i<<endl;
}
}
}
}
mn=min(mn,dp[i][b]);
}
//cout<<dp[i][b]<<endl;
if(mn==inf)
cout<<"Impossible"<<endl;
else
printf("%.3f\n",mn);
}
}
Doing Homework
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=15+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int n;
string s[MAX_N];
int dead[MAX_N];
int day[MAX_N];
int dp[1<<16];
int now[1<<16];
int pre[1<<16];
int ans[MAX_N];
int main()
{
INIT();
int t;
cin>>t;
while(t--)
{
cin>>n;
int i;
for(i=1; i<=n; i++)
{
cin>>s[i]>>dead[i]>>day[i];
}
fill(dp,dp+1+(1<<n),inf);
me(now,0);
dp[0]=0;
int mn=INF;
for(i=0; i<=(1<<n)-1; i++)
{
for(int j=1; j<=n; j++)
{
if(((i>>(j-1))&1)==0)
{
int p=0;
if(now[i]+day[j]>dead[j])
{
p=now[i]+day[j]-dead[j];
}
if(dp[i]+p<dp[i^(1<<(j-1))])
{
dp[i^(1<<(j-1))]=dp[i]+p;
now[i^(1<<(j-1))]=now[i]+day[j];
pre[i^(1<<(j-1))]=j;
//cout<<1<<endl;
}
}
}
}
cout<<dp[(1<<n)-1]<<endl;
int flag=(1<<n)-1;
int pos=0;
while(flag)
{
int x=pre[flag];
ans[pos++]=x;
flag=flag^(1<<(pre[flag]-1));
}
for(i=pos-1;i>=0;i--){
cout<<s[ans[i]]<<endl;}
}
return 0;
}
poj 2411 Mondriaan’s Dream
这题优先级的问题可坑死我了，==的优先级高于&，一定要记得加括号！！！
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=15+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
ll dp[13][13][1<<13];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)&&n)
{
me(dp,0);
dp[0][m][(1<<m)-1]=1;
int i,j,k;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
int pi,pj;
if(j==1)
{
pi=i-1;
pj=m;
}
else
{
pi=i;
pj=j-1;
}
for(k=0; k<(1<<m); k++)
{
if(1&(k>>(m-1))==1)
{
dp[i][j][(k<<1)^(1<<m)]+=dp[pi][pj][k];
//cout<<((k<<1)^(1<<m))<<endl;
//cout<<j<<' '<<k<<endl;
}
if(i>1&&(1&(k>>(m-1))==0))
{
dp[i][j][(k<<1)+1]+=dp[pi][pj][k];
//cout<<((k<<1)+1)<<endl;
}
if(j>1&&((1&(k>>(m-1)))==1)&&((k&1)==0))
{
//cout<<1<<endl;
dp[i][j][((k+1)<<1)^(1<<m)+1]+=dp[pi][pj][k];
//cout<<(((k+1)<<1)^(1<<m)+1)<<endl;
}
}
}
}
cout<<dp[n][m][(1<<m)-1]<<endl;
}
}
京公网安备 11010502036488号