[POJ 1661]help jimmy
36857 단어 dp
1
60 822 302 50
813 823 298
813 823 293
816 826 213
816 826 178
817 827 218
813 823 148
821 831 73
814 824 248
813 823 283
815 825 158
819 829 58
814 824 13
813 823 28
819 829 233
814 824 43
773 783 293
821 831 93
818 828 268
816 826 198
818 828 113
814 824 208
816 826 68
821 831 133
794 804 248
814 824 108
829 839 28
818 828 143
844 854 298
802 812 133
801 811 28
818 828 238
817 827 8
816 826 48
820 830 3
819 829 288
822 832 138
820 830 183
855 865 13
777 787 268
820 830 63
789 799 28
822 832 33
855 865 213
779 789 208
836 846 248
806 816 33
821 831 263
818 828 83
846 856 263
789 799 68
854 864 8
854 864 283
801 811 298
805 815 143
822 832 23
821 831 173
813 823 153
858 868 138
818 828 98
839 849 133
//ans : 352
AC 코드:
#include
#include
#include
#define debug(x) cout<
#define pb push_back
using namespace std;
typedef long long ll;
ll t,n,x,y,maxn;
const int N = 1e3 + 5;
const ll INF = (1LL<<55);
ll dpl[N],dpr[N],update_l[N],update_r[N];
struct plate{
ll l,r,h;
plate(ll _l,ll _r,ll _h):l(_l),r(_r),h(_h){
}
bool operator<(const plate & p) const{
if(h != p.h)return h < p.h;
else return l < p.l;
}
};
ll ans;
vector<plate> v;
int start = -1;
void init(){
v.clear();
for(int i = 0;i < n;i++){
dpl[i] = dpr[i] = INF;
update_l[i] = update_r[i] = 0;
}
start = -1;
ans = INF;
}
#define dbg 0
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#if dbg
freopen("input.txt","r",stdin);
#endif
cin>>t;
while(t--){
cin>>n>>x>>y>>maxn;
init();
for(int i = 0;i < n;i++){
int pl,pr,ph;
cin>>pl>>pr>>ph;
v.pb(plate(pl,pr,ph));
}
sort(v.begin(),v.end());
for(int i = v.size() - 1;i >= 0;i--){
if(y >= v[i].h && v[i].l <= x && v[i].r >= x){
start = i;
dpl[i] = x - v[i].l + y - v[i].h;
dpr[i] = v[i].r - x + y - v[i].h;
break;
}
}
if(start == -1){
cout<<y<<endl;
continue;
}
for(int i = start;i >= 0;i--){
bool l_up = false,r_up = false;
for(int j = i - 1;j >= 0;j--){
if(v[j].h == v[i].h)continue;
if((v[i].l >= v[j].l && v[i].l <= v[j].r)&&!l_up){
if(v[i].h - v[j].h <= maxn){
dpl[j] = min(dpl[j],v[i].h - v[j].h + v[i].l - v[j].l + dpl[i]);
dpr[j] = min(dpr[j],v[i].h - v[j].h + v[j].r - v[i].l + dpl[i]);
}
l_up =true;
}
if((v[i].r >= v[j].l && v[i].r <= v[j].r)&&!r_up){
if(v[i].h - v[j].h <= maxn){
dpl[j] = min(dpl[j],v[i].h - v[j].h + v[i].r - v[j].l + dpr[i]);
dpr[j] = min(dpr[j],v[i].h - v[j].h + v[j].r - v[i].r + dpr[i]);
}
r_up =true;
}
}
}
for(int i = start;i >= 0;i --){
for(int j = i - 1;j >= 0;j--){
if(v[i].l >= v[j].l && v[i].l <= v[j].r)update_l[i] = 1;
if(v[i].r >= v[j].l && v[i].r <= v[j].r)update_r[i] = 1;
}
}
for(int i = 0;i <= start;i++){
if(!update_l[i] && v[i].h <= maxn){
ans = min(dpl[i] + v[i].h,ans);
}
if(!update_r[i] && v[i].h <= maxn){
ans = min(dpr[i] + v[i].h,ans);
}
}
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.