本文主要是介绍DAG动规 uva，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
uva-1025题目网址
s
#include <iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>using namespace std;
const int inf=0x3f3f3f3f;
const int maxt=2000+5;
const int maxn=500+5;
int dp[maxt][maxn];
int have[maxt][maxn][5];
int t,n;
int m1,m2;
int tim[maxn];
int go[maxn][3];
int main()
{int ka=0;while(cin>>n&&n){ka++;memset(have,0,sizeof(have));memset(dp,0,sizeof(dp));cin>>t;for(int i=1;i<=n-1;i++)cin>>tim[i];cin>>m1;for(int i=0;i<m1;i++){int t;cin>>t;have[t][1][0]=1;for(int i=1;i<=n-1;i++){t+=tim[i];have[t][i+1][0]=1;}}cin>>m2;for(int i=0;i<m2;i++){int t;cin>>t;have[t][n][1]=1;for(int i=n-1;i>=0;i--){t+=tim[i];have[t][i][1]=1;}}for(int i = 1; i< n; i++)dp[t][i]=inf;dp[t][n]=0;for(int i=t-1;i>=0;i--)for(int j=1;j<=n;j++){dp[i][j]=dp[i+1][j]+1;if(j<n&&have[i][j][0]&&i+tim[j]<=t)dp[i][j]=min(dp[i][j],dp[i+tim[j]][j+1]);if(j>1&&have[i][j][1]&&i+tim[j-1]<=t)dp[i][j]=min(dp[i][j],dp[i+tim[j-1]][j-1]);}printf("Case Number %d: ",ka);if(dp[0][1]<inf)printf("%d\n",dp[0][1]);elseprintf("impossible\n");}return 0;
}
uva -437
#include <iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>using namespace std;const int maxn=200;
struct node
{int x,y,z;node(int xx=0,int yy=0,int zz=0){x=xx;y=yy;z=zz;}
};
node s[maxn];
int eg[maxn][maxn];
int fu[maxn];
int n;
int oj(int i,int j)
{int x1=min(s[i].x,s[i].y),x2=min(s[j].x,s[j].y);int y1=max(s[i].x,s[i].y),y2=max(s[j].x,s[j].y);if(x1<x2&&y1<y2)return 1;elsereturn 0;
}
int dfs(int x)
{if(fu[x]!=-1)return fu[x];fu[x]=s[x].z;for(int i=0;i<n;i++){if(eg[i][x])fu[x]=max(fu[x],dfs(i)+s[x].z);}return fu[x];
}
int main()
{int ka=0;while(cin>>n&&n){ka++;memset(fu,-1,sizeof(fu));for(int i=0;i<n;i++){int x,y,z;cin>>x>>y>>z;s[i].x=x; s[i].y=y; s[i].z=z;s[i+n].x=x; s[i+n].y=z; s[i+n].z=y;s[i+2*n].x=z; s[i+2*n].y=y; s[i+2*n].z=x;}n*=3;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){eg[i][j]=oj(i,j);eg[j][i]=oj(j,i);}int ans=0;for(int i=0;i<n;i++){int k=dfs(i);if(k>ans)ans=k;}printf("Case %d: maximum height = %d\n",ka,ans);}return 0;
}
UVA-1347
;
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cmath>using namespace std;const int maxn=1000+5;
const int inf=0x3f3f3f3f;
struct node
{double x,y;node(double xx=0,double yy=0):x(xx),y(yy){}bool operator<(const node & S)const{return x<S.x;}};
node s[maxn*2];
double dp[maxn][maxn];
double dist[maxn][maxn];
double get(int i,int j)
{//cout<<(s[i].x-s[j].x)*(s[i].x-s[j].x)-(s[i].y-s[j].y)*(s[i].y-s[j].y)<<endl;return sqrt((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y));
}
int main()
{int n;while(cin>>n){memset(dp,0,sizeof(dp));memset(dist,0,sizeof(dist));for(int i=1;i<=n;i++){cin>>s[i].x>>s[i].y;// cout<<s[i].x<<" "<<s[i].y;}sort(s+1,s+n+1);for(int i=2;i<=n;i++)for(int j=1;j<=i;j++){dist[i][j]=dist[j][i]=get(i,j);// cout<<dist[i][j]<<endl;}for(int i = n - 1; i > 1; i--)for(int j = 1; j < i; j++){if(i==n-1)dp[i][j] = dist[j][n]+dist[i][n];else dp[i][j]= min( dp[i+1][j]+dist[i][i+1],dp[i+1][i]+dist[i+1][j]);}printf("%.2f\n",dp[2][1]+dist[2][1]);}return 0;
}
这篇关于DAG动规 uva的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
