首页 > 代码库 > 20141022

20141022

2024-07-28 17:38:35   218人阅读

　　

　　TYVJ1125  JR‘s chop

　　http://www.tyvj.cn/Problem_Show.aspx?id=1125

　　先将每根筷子按长度排序

　　设dp[i][j][0]为前i个筷子取j对且不取第i个的最小解

　　　dp[i][j][1]为前i个筷子取j对且取第i个的最小解

　　　dp[i][j][0] = min(dp[]i-1[j][0],dp[i-1][j][1])

　　　dp[i][j][1] = min(dp[k][j-1][0],dp[k][j-1][1])+b[i][k+1] | (j-1)*2<=k<=i-2

　　　b[i][k] 为第i个和第k个筷子的平方差的和

 

 

　　

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 const int maxn = 105; 8 const int maxv = 1005; 9 const int INF = 0x3f3f3f3f;10 const int mod = 1e9+7;11 typedef long long LL;12 int a[maxn],dp[maxn][maxn][2];13 int b[maxn][maxn];14 int main()15 {16 //    freopen("in.txt","r",stdin);17     int n,m;18     while(cin>>n>>m)19     {20         m+=3;21         if(n<m*2){22             printf("-1\n");23             break;24         }25         memset(dp,0x3f,sizeof(dp));26         memset(b,0,sizeof(b));27         for(int i = 1;i<=n;++i)scanf("%d",a+i);28         sort(a+1,a+1+n);29         for(int i = 1;i<=n;++i)for(int j = 1;j<=i;++j)30             b[i][j] = (a[i]-a[j])*(a[i]-a[j]);31         dp[2][0][1] = 0;32         dp[2][1][1] = b[2][1];33         for(int i = 3;i<=n;++i)34             for(int j = 1;j<=i/2;++j)35             {36                 dp[i][j][0] = min(dp[i-1][j][0],dp[i-1][j][1]);37                 for(int k = (j-1)*2;k<=i-2;k++)38                 {39                     int t = min(dp[k][j-1][1],dp[k][j-1][0])+b[i][k+1];40                     dp[i][j][1] = min(t,dp[i][j][1]);41                 }42             }43         printf("%d\n",min(dp[n][m][0],dp[n][m][1]));44     }45     return 0;46 }

 

 

　　　　TYVJ 1213 嵌套矩形

　　　　http://www.tyvj.cn/Problem_Show.aspx?id=1213

　　　　水题

 

　　　　

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 const int maxn = 2005; 8 const int maxv = 1005; 9 const int INF = 0x3f3f3f3f;10 const int mod = 1e9+7;11 typedef long long LL;12 struct node13 {14     int x;15     int y;16 }a[maxn];17 int cmp(const void *a,const void *b)18 {19     struct node *aa = (struct node *)a;20     struct node *bb = (struct node *)b;21     if(aa->x==bb->x)return aa->y-bb->y;22     return aa->x-bb->x;23 }24 int dp[maxn];25 int main()26 {27 //    freopen("in.txt","r",stdin);28     int n;scanf("%d",&n);29     for(int i = 1;i<=n;++i)30     {31         int x,y;32         scanf("%d%d",&x,&y);33         if(x>y)swap(x,y);34         a[i].x = x;35         a[i].y = y;36     }37     qsort(a+1,n,sizeof(a[1]),cmp);38 39     for(int i = 1;i<=n;++i)40     {41         dp[i] = 1;42         for(int j = 1;j<i;++j)if(a[i].x>a[j].x && a[i].y>a[j].y)43             dp[i] = max(dp[i],dp[j]+1);44     }45     int ans = 0;46     for(int i = 1;i<=n;++i)47         ans = max(ans,dp[i]);48     cout<<ans<<endl;49     return 0;50 }

 　　　　

 

　　　　TYVJ1095 美元

　　　　http://www.tyvj.cn/Problem_Show.aspx?id=1095

 

　　　　水题

　　　　设dp[i][0]表示第i天以美元为单位最多的钱

　　　　　dp[i][1]表示第i天以马克为单位最多的钱

　　　　

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 const int maxn = 2005; 8 const int maxv = 1005; 9 const int INF = 0x3f3f3f3f;10 const int mod = 1e9+7;11 typedef long long LL;12 double dp[maxn][2];13 int main()14 {15 //    freopen("in.txt","r",stdin);16     int n;cin>>n;17     for(int i = 1;i<=n;++i)18     {19         int t;scanf("%d",&t);20         if(i==1)21         {22             dp[i][0] = 100;23             dp[i][1] = t*1.0;24             continue;25         }26         dp[i][0] = max(dp[i-1][0],dp[i-1][1]/t*100);27         dp[i][1] = max(dp[i-1][1],dp[i-1][0]/100*t);28     }29     printf("%.2lf\n",dp[n][0]);30     return 0;31 }

 

20141022


联系
我们