首页 > 其他 > 详细

877C

时间:2017-10-24 10:36:04      阅读:560      评论:0      收藏:0      [点我收藏+]

构造

想了好长时间。。。

答案是n+n/2

我们这么想,先把偶数位置炸一遍,所有坦克都在奇数位置,然后再把奇数炸一遍,坦克都到偶数去了,然后再炸一次偶数就都炸掉了。。。

好巧妙啊 奇偶讨论很重要

技术分享
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 1005;
int n, m;
double dp[N][N], a[N][N][3];
double dfs(int x, int y)
{
    if(x == n && y == m) return 0.0;
    if(x > n || y > m) return 0.0;
    if(fabs(1.0 - a[x][y][0]) < 1e-8) return 0.0;
    if(dp[x][y] >= 0.0) return dp[x][y];
    dp[x][y] = dfs(x, y + 1) * a[x][y][1] + dfs(x + 1, y) * a[x][y][2] + 2.0;
    dp[x][y] /= 1.0 - a[x][y][0];
    return dp[x][y]; 
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {        
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)    
            {
                dp[i][j] = -1.0;
                for(int k = 0; k < 3; ++k) scanf("%lf", &a[i][j][k]);
            }
        printf("%.3f\n", dfs(1, 1));        
    }    
    return 0;
}
View Code

 

877C

原文:http://www.cnblogs.com/19992147orz/p/7722087.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!