HDU 4576 简单概率 + 滚动数组DP(大坑)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4576

坑大发了,居然加 % 也会超时;

 #include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define repd(i, a, b) for(int i = b; i >= a; i--)
#define sfi(n) scanf("%d", &n)
#define sfl(n) scanf("%I64d", &n)
#define pfi(n) printf("%d\n", n)
#define pfl(n) printf("%I64d\n", n)
#define MAXN 1000005
int n, l, m, r, d;
int t = , mm;
double dp[][];
int main()
{
while(~scanf("%d%d%d%d", &n, &m, &l, &r) && (n + m + l + r))
{
t = ;
repu(i, , n + ) dp[][i] = 0.0;
dp[][] = 1.0;
int c;
repu(i, , m)
{
sfi(d);
if(l == && r == n) continue;
c = d / n;
mm = d - n * c;
if(mm)
{
t = !t;
repu(j, , n + )
{
int lt, rt;
if((n + (j - mm)) >= n) lt = (n + (j - mm)) - n;
else lt = (n + (j - mm));
if((j + mm) >= n) rt = (j + mm) - n;
else rt = (j + mm);
if(lt == ) lt = n;
if(rt == ) rt = n;
dp[t][j] = (dp[!t][lt] + dp[!t][rt]) / 2.0;
//cout<<j<<" :"<<dp[t][j]<<endl;
}
}
}
double ans = 0.0;
if(l == && r == n) ans = 1.0;
else
repu(i, l, r + ) ans += dp[t][i];
printf("%.4lf\n", ans);
}
return ;
}

AC

 #include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define repd(i, a, b) for(int i = b; i >= a; i--)
#define sfi(n) scanf("%d", &n)
#define sfl(n) scanf("%I64d", &n)
#define pfi(n) printf("%d\n", n)
#define pfl(n) printf("%I64d\n", n)
#define MAXN 1000005
int n, l, m, r, d;
int t = , mm;
double dp[][];
int main()
{
while(~scanf("%d%d%d%d", &n, &m, &l, &r) && (n + m + l + r))
{
t = ;
repu(i, , n + ) dp[][i] = 0.0;
dp[][] = 1.0;
int c;
repu(i, , m)
{
sfi(d);
if(l == && r == n) continue;
c = d / n;
mm = d - n * c;
if(mm)
{
t = !t;
repu(j, , n + )
{
int lt, rt;
lt = (n + (j - mm)) % n;
rt = (j + mm) % n;
// if((n + (j - mm)) >= n) lt = (n + (j - mm)) - n;
// else lt = (n + (j - mm));
// if((j + mm) >= n) rt = (j + mm) - n;
// else rt = (j + mm);
if(lt == ) lt = n;
if(rt == ) rt = n;
dp[t][j] = (dp[!t][lt] + dp[!t][rt]) / 2.0;
//cout<<j<<" :"<<dp[t][j]<<endl;
}
}
}
double ans = 0.0;
if(l == && r == n) ans = 1.0;
else
repu(i, l, r + ) ans += dp[t][i];
printf("%.4lf\n", ans);
}
return ;
}

TLE

% 慎用啊必须,虽然不知道为什么

上一篇:Making the Grade_滚动数组&&dp


下一篇:Gym 100507G The Debut Album (滚动数组dp)