递推计数-hdu-4747-Mex
题目大意:给n个数,求所有区间内没有出现的最小非负整数和。
解题思路:
首先感谢大神博客:http://www.cnblogs.com/xin-hua/p/3325154.html可以解释的太少了。
我再解释一遍。
首先要明白,以i结束的所有区间的值的和记为f[i]肯定不超过以i+1结束的所有区间的值的和记为f[i+1]。
所以可以根据f[i]间接推出f[i+1],记第i个数为sa[i],显然只用考虑大于等于sa[i]的数j对f[i]=f[i-1]+?的影响,。如果j出现在1~i-1区间中,比较j最晚出现的位置与覆盖完全的1~j-1的最小位置的较小位置k,那么区间j的前一次出现的位置到k位置这个区间内所有点到i位置的值都+1.
这样逐次累加,直到不影响为止。
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #define eps 1e-6 #define INF 0x3fffffff #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 210000 int sa[Maxn],pos[Maxn],full[Maxn]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while(scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) scanf("%d",&sa[i]); memset(pos,0,sizeof(pos)); memset(full,0,sizeof(full)); int last; ll tt=0,ans=0; for(int i=1;i<=n;i++) { if(sa[i]<n)// { last=pos[sa[i]];//前一个sa[i]的最晚位置 pos[sa[i]]=i; //最晚位置 for(int j=sa[i];j<n;j++) { if(j) //考虑j对前面区间的影响 full[j]=min(full[j-1],pos[j]); // else full[j]=i; if(full[j]>last) tt+=full[j]-last; //last+1到full[j]区间内所有点到i的值+1,逐次累加 else break; } } printf("i:%d %I64d\n",i,tt); ans+=tt; } printf("%I64d\n",ans); } return 0; }
补充:软件开发 , C++ ,