ACMboy

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2010年4月12日 #

城市规划

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:153            测试通过:46

描述

NanJing准备开发一片荒地,目前已经规划好了一些居民点,还要建设道路。由于经费问题,现在想在保持任意两点间的距离最短的前提下,用尽可能少的经费把这些点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。现在给出两两居民点间的花费,当然了,花费和路径长度成正比~

 

输入

第一行是个N<=100,表示N个居民点。

下面是个N*N的矩阵,第i行第j列,表示ij的花费,可能有负数,表示两地不相连。保证有解。

 

输出

输出一行为总花费。

 

样例输入

3
0 2 1
2 0 3
1 3 0

样例输出

3

QQ:765391213

  #include <stdio.h>
#include 
<string.h>
const int MAXN=100;
const int MAXINT=10001;
int n,dis[MAXN][MAXN],flag[MAXN][MAXN];
int main()
{
    scanf(
"%d",&n);
    
int k,i,j,temp;
    
for(i=0;i<n;i++)
        
for(j=0;j<n;j++)
        
{
            scanf(
"%d",&dis[i][j]);
            
if(dis[i][j]<0)
                dis[i][j]
=MAXINT;
        }

        
for(i=0;i<n;i++)
            
for(j=0;j<n;j++)
                flag[i][j]
=1;
            
for(k=0;k<n;k++)
                
for(i=0;i<n;i++)
                
{
                    
if(i==k) continue;
                    
for(j=0;j<n;j++)
                    
{
                        
if(k==j)continue;
                        temp
=dis[k][j]+dis[i][k];
                        
if(temp<=dis[i][j]){
                            flag[i][j]
=0;
                            dis[i][j]
=temp;
                        }

                    }

                }

                
int ans=0;
                
for(i=0;i<n;i++)for(j=i+1;j<n;j++)
                    
if(flag[i][j]) ans+=dis[i][j];
                    printf(
"%d\n",ans);
                    
return 0;
}
posted @ 2010-04-12 12:19 EG-HUA 阅读(197) | 评论 (0)编辑 收藏

2010年4月9日 #

                                                               越大越聪明吗?
                 这是一道动态规划题目,这里只提供个人代码:

#include <iostream>
struct elephone
{
    
int weight,iq,num;
}
;
int k,s[1001],max=0,vis[1001],S[1001],dp[1001][1001];
elephone a[
1000];

void dpf(int i,int j)
{
    
int &ans=dp[i][j];
    
if(ans!=-1return;
    ans
=1;
    s[j]
=a[i].num+1;
    
if(j>max) {for(int q=1;q<=j;q++) S[q]=s[q];max=j;}
    
for(int p=0;p<k;p++)
    
{
        
if(!vis[p]&&a[p].weight>a[i].weight&&a[p].iq<a[i].iq)
        
{
            vis[p]
=1;
            dpf(p,j
+1);
            vis[p]
=0;
        }

    }

}

int main()
{
    
int i=0;
    memset(dp,
-1,sizeof(dp));
    memset(vis,
0,sizeof(vis));
    
while(scanf("%d%d",&a[i].weight,&a[i].iq)==2)
    
{
        a[i].num
=i;
        
++i;
    }

    k
=i;
    
for(int q=0;q<k;q++)
    
{
    vis[q]
=1;
    dpf(q,
1);
    vis[q]
=0;
    }

    printf(
"%d\n",max);
    
for(int r=1;r<=max;r++)
        printf(
"%d\n",S[r]);
    
return 0;
}





         
posted @ 2010-04-09 13:58 EG-HUA 阅读(78) | 评论 (0)编辑 收藏

    一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱时空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N(N可以为零),油站i离出发点的距离Di、每升汽油价格Pi(i=1,2,……,N)。

计算结果四舍五入至小数点后两位。

如果无法到达目的地,则输出“No Solution”。

样例:

Input

D1=275.6 C=11.9      D2=27.4     P=2.8   N=2

油站号I

离出发点的距离Di

每升汽油价格Pi

1

102.0

2.9

2

220.0

2.2

Output

26.95(该数据表示最小费用)

代码:

#include <iostream>
int main()
{
    
double rest=0,need,p[12],s,c,t,d[12];
    
int n;
    scanf(
"%lf%lf%lf%lf%d",&s,&c,&t,&p[0],&n);
    
for(int i=1;i<=n;i++)
        scanf(
"%lf%lf",&d[i],&p[i]);
    d[
0]=0;
    d[n
+1]=s;
    
int k=0,j=0,min=0,min2=0,back=0;
    
double cost=0;
    
while(k<=n)
  
{
        j
=k;
        
while(d[j+1]-d[k]<=c*t&&j<=n)
      
{
            j
++;
            
if(min==0&&p[j]<p[k]) min=j;
            
if(min2==0||p[j]<p[min2]) min2=j;
        }

        
if(j==k)
      
{
            printf(
"No Solution\n");
            
return 0;
        }

        
if(!min)
      
{
            need
=c-rest;
            cost
+=need*p[k];
            rest
=c-(d[min2]-d[k])/t;
            k
=min2;
        }

        
else
        
{
            need
=(d[min]-d[k])/t-rest;
            
if(need<0)
                need
=0;
            cost
+=need*p[k];
            rest
=0;
            k
=min;
        }

        min
=min2=0;
    }

    printf(
"%.2lf\n",cost);
    
return 0;
}
posted @ 2010-04-09 13:48 EG-HUA 阅读(823) | 评论 (0)编辑 收藏

2010年4月6日 #

                                          金明的预算方案

                                             
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

主件

附件

电脑

打印机,扫描仪

书柜

图书

书桌

台灯,文具

工作椅

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1j2,……,jk,则所求的总和为:

v[j1]*w[j1]+v[j2]*w[j2]+ +v[jk]*w[jk]。(其中*为乘号)

请你帮助金明设计一个满足要求的购物单。

输入

1行,为两个正整数,用一个空格隔开:

N m

(其中N<32000)表示总钱数,m<60)为希望购买物品的个数。)

从第2行到第m+1行,j行给出了编号为j-1的物品的基本数据,每行有3个非负整数

v p q

(其中v表示该物品的价格(v<10000),p表示该物品的重要度(1~5),q表示该物品是主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号)

输出

只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。

样例输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出

2200





#include 
<iostream>
const int Maxn=32000;
const int Maxm=60;
int maxvalue[Maxn][Maxm],Main[60];
int v[Maxm][3];
int w[Maxm][3],n,m;
int GetNeedMoney(int item,int idea)
{
    
int needmoney=0;
    
switch(idea)
    {
    
case 1:
        needmoney=w[item][0];
        
break;
    
case 2:
        needmoney=w[item][0]+w[item][1];
        
break;
    
case 3:
        needmoney=w[item][0]+w[item][2];
        
break;
    
case 4:
        needmoney=w[item][0]+w[item][1]+w[item][2];
        
break;
    
case 5:
        needmoney=0;
        
break;
    }
    
return needmoney;
}
int GetItemMaxValue(int money,int item,int idea)
{
    
int itemvalue=0;
    
if(money>=GetNeedMoney(item,idea))
    {
        
switch(idea)
        {
        
case 1:
            itemvalue=v[item][0];
            
break;
        
case 2:
            itemvalue=v[item][0]+v[item][1];
            
break;
        
case 3:
            itemvalue=v[item][0]+v[item][2];
            
break;
        
case 4:
            itemvalue=v[item][0]+v[item][1]+v[item][2];
            
break;
        
case 5:
            itemvalue=0;
            
break;
        }
    }
    
return itemvalue;
}
int GetMaxValue(int money,int item)
{
    
int &ans=maxvalue[money][item];
    
int max=0,tmp;
    
if(ans!=-1)
    {
        
return ans;    
    }
    
if(item==1)
    {
        
for(int j=1;j<=5;j++)
        {
            tmp=GetItemMaxValue(money,item,j);
            
if(max<tmp)
                max=tmp;
        }
    }
    
else  
        
        
for(int i=1;i<=5;i++)
        {
            
int usedmoney=GetNeedMoney(item,i);
            
if(money>=usedmoney)
            {
                tmp=GetItemMaxValue(usedmoney,item,i)+GetMaxValue(money-usedmoney,item-1);
                
if(max<tmp)
                    max=tmp;
            }
        }
        
return ans=max;
}
int main()
{
    
int value,p,q,MaxItem=0;
    memset(maxvalue,-1,
sizeof(maxvalue));
    memset(v,0,
sizeof(v));
    scanf("%d%d",&m,&n);
    
for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&value,&p,&q);
        
if(q==0)
        {
            ++MaxItem;    
            v[MaxItem][0]=value*p;
            w[MaxItem][0]=value;
            Main[i]=MaxItem;
        }
        
else
        {              
            
int MainOrder=Main[q];
            
if(v[MainOrder][1]==0)
            {
                v[MainOrder][1]=value*p;
                w[MainOrder][1]=value;
            }
            
else
            {
                v[MainOrder][2]=value*p;
                w[MainOrder][2]=value;
            }
        }
    }
    n=MaxItem;
    printf("%d\n",GetMaxValue(m,n));
    
return 0;
}

posted @ 2010-04-06 22:55 EG-HUA 阅读(745) | 评论 (0)编辑 收藏